Print Nodes in Top View of a Binary Tree

Posted by N.K. Chauhan on Mar 31, 2024

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).

Complexity
The time complexity of this solution is O(n) and space complexity is O(n) due to auxiliary Map.

Related


Find the diameter or width of a binary tree

Pre-order Tree Traversal - Iterative and Recursive

Print the left view of a binary tree

Write a program to print height/depth of a Binary Tree

Level Order or Breadth First traversal of Binary Tree

Print/Traverse a Binary Tree in Zigzag Order

Print a Binary Tree in Vertical Order

Create a mirror tree from a given binary tree

In-order Tree Traversal - Iterative and Recursive

Print diagonal traversal of a binary tree