## Similar Problems

Similar Problems not available

# Vertical Order Traversal Of A Binary Tree - Leetcode Solution

## Companies:

LeetCode: Vertical Order Traversal Of A Binary Tree Leetcode Solution

Difficulty: Hard

Topics: hash-table depth-first-search breadth-first-search tree binary-tree

Problem statement:

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples:

Example 1: Input: [3,9,20,null,null,15,7]

3
/

9 20
/

15 7

Output: [ [9], [3,15], [20], [7] ]

Explanation:

- The top-down view of the tree is [9], [3,15], [20], [7]
- In the vertical (column) order traversal, we should first visit the leftmost node (9), then the middle column node (3 and 15), and finally the rightmost node (20 and 7).

Example 2: Input: [1,2,3,4,5,6,7]

```
1
```

/

2 3
/ \ /

4 5 6 7

Output: [ [4], [2], [1,5,6], [3], [7] ]

Explanation:

- The top-down view of the tree is [4], [2], [1,5,6], [3], [7]
- In the vertical (column) order traversal, we should first visit the leftmost node (4), then the left column node (2), then the middle column node (1, 5, and 6), and finally the rightmost node (3 and 7).

Approach:

To solve this problem, we can use map and queue. We can traverse through the tree level by level using a queue and keep track of the columns using a map.

Let's say we have a current node with value val and column index col. We can add this node's value to the column in the map with key col.

- For the left child node, we can add its value to the column col-1.
- For the right child node, we can add its value to the column col+1.
- We also need to keep track of the minimum and maximum column index for all nodes in the tree. This will help us in iterating through the map keys to get the columns in order.

After we have added all the nodes to the map, we can iterate through the map from the minimum column index to the maximum column index and add all the column values to a 2D array, which we will return as the answer.

Solution:

Let's look at the code for the above approach:

C++ Code:

class Solution { public: vector<vector<int>> verticalTraversal(TreeNode* root) {

```
// Map to keep all nodes' values in their respective columns
map<int, vector<pair<int,int>>> m;
// Queue to traverse the tree level by level
queue<pair<TreeNode*,pair<int,int>>> q;
// Starting from the root node with column index 0 and row index 0
q.push(make_pair(root,make_pair(0,0)));
// Column minimum and maximum values
int colMin = INT_MAX, colMax = INT_MIN;
// Traverse until queue is empty
while(!q.empty()) {
// Get values from front of queue
auto front = q.front();
q.pop();
TreeNode* node = front.first;
int col = front.second.first;
int row = front.second.second;
// Add node to map column
m[col].push_back(make_pair(row,node->val));
// Update column minimum and maximum values
colMin = min(colMin,col);
colMax = max(colMax,col);
// Insert left child to queue
if(node->left) q.push(make_pair(node->left,make_pair(col-1,row+1)));
// Insert right child to queue
if(node->right) q.push(make_pair(node->right,make_pair(col+1,row+1)));
}
// Create result 2D array
vector<vector<int>> res;
// Iterate through columns in map
for(int i=colMin;i<=colMax;i++) {
// Get all nodes of current column
auto colNodes = m[i];
// Sort the nodes based on row and value
sort(colNodes.begin(),colNodes.end());
// Add current column nodes to result row
vector<int> rowNodes;
for(auto p:colNodes) rowNodes.push_back(p.second);
// Add current row to result 2D array
res.push_back(rowNodes);
}
return res;
}
```

};

Time Complexity:

The time complexity of the above solution is O(nlogn), where n is the number of nodes in the tree. This is because we are iterating through the tree level by level, and sorting the nodes in each column, which takes O(logn) time. Since we do this for all n nodes, the overall time complexity is O(nlogn).

Space Complexity:

The space complexity of the above solution is O(n), where n is the number of nodes in the tree. This is because we are using a map to store all nodes in their respective columns, which could have up to n elements in the worst case. Additionally, we are using a queue to traverse the tree level by level, which could have up to n/2 elements in the worst case. Therefore, the overall space complexity is O(n).

## Vertical Order Traversal Of A Binary Tree Solution Code

`1`