Vertical Order Traversal of a Binary Tree

This is a LeetCode question asked by Facebook, Amazon, Apple, Google & Microsoft.

Basically in this question we have to traverse the tree from left to right and top to bottom. Whenever we move to left column number decreases & on going to right it increases. When more than one element has same column number then we check for values. In that case lesser value is preferred first. 

 

Like in case of [1, 5, 6] . All had column number 0 so they were arranged in ascending order. You can understand this concept by looking the below image :

 

 

 

In this question we will use DFS approach of traversal. Which you can do using inorder, postorder and preorder

 

Now we will start traversal from root (it has value = 1, row number = 0, column number = 0) & we will also maintain global cache which will have key = column number & value = vector of element in that column number.

For the given root our cache = { 0 : { 0, 1 }} here 1st zero is column number, 2nd zero row number & 1 is value of root.

Next we will go to another row. Our cache = { -1 : { 1, 2 }} and we will repeat like & finally our cache will look like :

 

We will also keep track of smallest column that we encountered & also largest.

Now coming to code.

1. We will pass root in the function & then do DFS on root which will built cache.
2. Then we will find minimum & maximum column number.
3. After this we will run our loop from minc to maxc & print the vector.
4. When we come across a case where more than one vector has same column number then we sort that & print in ascending order.

 

Solution

 

Here 1st int is column number & then row number followed by value.

 

unordered_map<int, vector<pair<int, int>>> cache;

 

As we go down towards left row will increase by 1 but column will decrease by 1.

 

dfs(node->left, r+1, c-1, cache, minC, maxC);

 

Since our comparision is is based on row number & when row number is equal then based on second number. So for sorting our comparator will take two pairs. If row number is less then simply return else return smaller element. This all is covered under our sort() function.