Top View of Binary Tree in Java

Given a binary tree we have to print top view. We will discuss our approach to solve this problem along with its implementation and code in Java language. We will also analyze the time and space complexity of our implementation.

The top view of binary tree means the set of nodes visible when the tree is viewed from top. In other words, a node is included in our top view if it is the topmost node at it’s respective horizontal distance.

We calculate the horizontal distance as follows:

  • The Horizontal Distance of Root of tree=0.
  •  Horizontal Distance of Left Child=Horizontal Distance of it’s Parent Node – 1.
  • The Horizontal Distance of Right Child=Horizontal Distance of it’s Parent Node + 1.

Let us consider binary tree give below:

Top View of Binary Tree in Java

The top view of this tree will give output:  2  1  3  6.

Explanation:

The nodes are highlighted in the figure above. We put nodes with same horizontal distance together. We start from the root node 1 at level 1 the horizontal distance is 0 at root, then we go down each level and print the topmost node for that horizontal distance. At level 2 node 2 is the topmost node with horizontal distance -1 so print it, at the same level 2 node 3 is the topmost node with horizontal distance 1. At level 3 node 6 is the topmost node with horizontal distance 2.

Approach (Using Level Order Traversal and Hashing)

The idea of our approach is to put nodes with same horizontal distance together. Then, print the topmost node with the respective horizontal distance. We get the topmost node by maintaining a map and doing level order traversal. At a particular level if the node with the given horizontal distance is not present in our map, we add the node’s hd as a key to our map and it’s data as the value. We maintain a pair class of node and hd to maintain each node’s hd and level in our Queue while processing them. We add a given hd only once which ensures only the topmost node is present in our map. Lastly, we print the values of the map. In order to print the top view from left to right we use a Tree Map to order the Map with respect to hd.

Note: We use the short form of horizontal distance of each node as hd.

Below is the implementation in Java:

Output:

Time Complexity: Now we analyze the time complexity of our approach. We do a level order traversal of all the nodes in O (n). Along with this, and each insertion in our Tree-Map takes O (log n) time. So the Overall time Complexity will be O (n*log n).

Space Complexity: The Queue we use to implement the level order traversal will at the most store the nodes present at all levels and if we are given a skewed binary tree then it will store nodes at all levels so the overall space complexity is O (n).

That’s it for the Top View of Binary tree you can try this approach and run the code in your IDE or Java compiler.

You can ask your queries in the comment section below.

Leave a Comment

Your email address will not be published.