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.
![Print The Top View of a Binary Tree.](/static/media/algorithms/2014/12/Print-The-Top-View-of-a-Binary-Tree.1.png)
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](/static/media/algorithms/2015/01/Vertical-Order-Sum-Implementation.png)
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/