Given a binary tree, print the top view of it.
The top view of a binary tree is the set of nodes visible when the tree is viewed from the top.
Example 1: Print top view of a Binary Tree
Input:
Output: 4,2,1,3,7
Solutions
Method 1: In O(n) using Map
The top view of a binary tree is the set of nodes visible when the tree is viewed from the top.
Or in other words, it is like printing very first or top element of every vertical of the tree (Vertical Traversal of Binary Tree).
We can do level order traversal of the given Binary Tree, while traversing, we can recursively calculate "Horizontal Distance".
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.
For every "Horizontal Distance" value, we maintain a list of nodes in a tree map.
At the end, print the first element of each map-value (list), while traversing the map in ascending order of "Horizontal Distance (Key)".
Note: We can even optimize this solution for space by storing only the first(top) value for each vertical, this can be achieved by storing values to Map only when there is no value present for that key (vertical).