This post is completed by 1 user

  • 0
Add to List
Medium

96. Print The Top View of a Binary Tree

What is Top View: Top view means when you look at the tree from the top the nodes you will see will be called the top view of the tree. See the example below.

Print The Top View of a Binary Tree.

As the example above shows,8, 4, 2, 1, 3, 7 is the Top view of the given binary tree.

Approach:

This approach is similar to the - Print the Binary Tree in Vertical Order Path

To categorize the tree elements vertically, use a variable named level. Increment level whenever you move left and decrement it whenever you move right.

level distribution

Following the steps above, the levels are now separated vertically. Next, you need to store the elements of each level. To do this, create a map or dictionary where the key-value pair represents the level and the element at that level, respectively.

Now, perform a level-order traversal, print, and store only the first visited node at each level.

For the level-order traversal or Breadth-First Search (BFS), utilize a simple queue technique. Create a class called QueuePack to store objects containing the node and its level.

Note: Use TreeMap in case want to print the bottom view in order.

Output:

 1   2   3   4   7   8

Reference: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/