Print nodes in vertical order of a given Binary Tree (Vertical Traversal)

Given a binary tree, perform vertical traversal of it. In vertical traversal, we print nodes of a binary tree in vertical order by assuming that the left and right child of a node makes 45 degree angle with the parent.

 

For example, vertical traversal of below binary tree is

2, 7
1, 5
3, 8
6

vertical-order
 


 

This problem can be easily solved with the help of Hashing. The idea is to create an empty map where each key represents the relative horizontal distance of a node from the root node and value in the map maintains all nodes present at same horizontal distance. Then we do a pre-order traversal of the tree and we update the map. For each node, we recurse for its left subtree by decreasing horizontal distance by 1 and recurse for right subtree by increasing horizontal distance by 1. For above binary tree, the final values in the map will be


(horizontal distance -> Nodes)

-1 -> [2, 7]
 0 -> [1, 5]
 1 -> [3, 8]
 2 -> [6]

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂