Given a binary tree, the task is to print it vertically, see the example below for illustration:
Example 1: Print Binary Tree in Vertical Order
Input:
Output:
4 2 1,5,6 3,8,9 7
Solutions
Method 1: In O(n) using Map
For this solution, we need to group nodes based on their Horizontal Distances from the root.
If two nodes have the same Horizontal Distance, then they are on the same vertical line.
Horizontal Distance for root is 0, a right node is considered at +1 horizontal distance and a left edge is considered at -1 horizontal distance.
We can do level order traversal of the given Binary Tree, while traversing, we can recursively calculate Horizontal Distance.
Let's pass the initial horizontal distance as 0 for root.
For left subtree, we pass the Horizontal Distance as "Horizontal distance of root" minus 1. For right subtree, we pass the Horizontal Distance as "Horizontal Distance of root" plus 1.
For every "Horizontal Distance" value, we maintain a list of nodes in a tree map.
At the end, print the map in ascending order of Horizontal Distance to get "Vertical Order" of the tree.