# Vertical Traversal - Tree

Aug 7th, 2020
1,858
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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), right(right) {}
10.  * };
11.  */
12. class Solution {
13. public:
14.     vector<vector<int>> verticalTraversal(TreeNode* root) {
15.         if(root==nullptr)   return {};
16.         unordered_map<int, vector<int>> xToVector;
17.
18.         queue<pair<TreeNode*, int>> q;
19.         q.push({root, 0});
20.         int leftBoundary = INT_MAX; int rightBoundary = INT_MIN;
21.
22.         pair<TreeNode*, int> temp;
23.
24.         unordered_map<int, set<int>> formedSoFar;
25.         int l_leftBoundary = INT_MAX, l_rightBoundary = INT_MIN;
26.
27.         while(!q.empty()){
28.             int qSize = q.size();
29.             while(qSize--){
30.                 //all these temp's have same y coordinate
31.                 temp = q.front(); q.pop();
32.
33.
34.                 l_leftBoundary = min(l_leftBoundary, temp.second);
35.                 l_rightBoundary = max(l_rightBoundary, temp.second);
36.
37.                 if((temp.first)->left != nullptr){
38.                     q.push({(temp.first)->left, temp.second-1});
39.                 }
40.                 if((temp.first)->right != nullptr){
41.                     q.push({(temp.first)->right, temp.second+1});
42.                 }
43.                 formedSoFar[temp.second].insert((temp.first)->val);
44.
45.             }
46.             leftBoundary = min(leftBoundary, l_leftBoundary);
47.             rightBoundary = max(rightBoundary, l_rightBoundary);
48.
49.             for(int i=l_leftBoundary; i<=l_rightBoundary; i++){
50.                 for(auto &vl: formedSoFar[i]){
51.                     xToVector[i].push_back(vl);
52.                 }
53.             }
54.
55.             formedSoFar.clear();
56.         }
57.         //cout << leftBoundary << " " << rightBoundary << endl;
59.
60.         for(int i=leftBoundary; i<=rightBoundary; i++){
61.             if(xToVector.count(i)){