1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 * int val;
5
 * TreeNode *left;
6
 * TreeNode *right;
7
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10
 * right(right) {}
11
 * };
12
 */
13
class Solution {
14
 public:
15
  // hd - horizontal distance
16
  // vertical order traversal starts from least hd to highest hd
17
  // on moving left hd decreases by 1, on moving right it increases by 1
18

19
  // should do level order traversal to get the nodes with same hd in correct
20
  // order
21

22
  vector<vector<int>> verticalTraversal(TreeNode *root) {
23
    map<int, vector<int>> mp;
24
    queue<pair<TreeNode *, int>> q;
25
    q.push({root, 0});
26
    while (!q.empty()) {
27
      int sz = q.size();
28
      map<int, multiset<int>> temp;
29
      for (int i = 0; i < sz; i++) {
30
        auto pr = q.front();
31
        q.pop();
32
        temp[pr.second].insert(pr.first->val);
33
        if (pr.first->left != NULL) {
34
          q.push({pr.first->left, pr.second - 1});
35
        }
36
        if (pr.first->right != NULL) {
37
          q.push({pr.first->right, pr.second + 1});
38
        }
39
      }
40
      for (auto pr : temp) {
41
        for (auto val : pr.second) {
42
          mp[pr.first].push_back(val);
43
        }
44
      }
45
    }
46
    vector<vector<int>> ans;
47
    for (auto pr : mp) {
48
      vector<int> temp;
49
      for (auto val : pr.second) {
50
        temp.push_back(val);
51
      }
52
      ans.push_back(temp);
53
    }
54
    return ans;
55
  }
56
};