# 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

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 –

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