|
This post is completed by 1 user
|
Add to List |
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.
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.
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/