Objective: – Given a binary tree, print it in the Top View of it.
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 you can see in the example above,8, 4, 2, 1, 3, 7 is the Top view of the given binary tree.
This approach is quite similar to the – Print the Binary Tree in Vertical Order Path. Just modified the code so that it will print only the first element it will encounter in the vertical order.
How will you know that you are visiting the first node at every level?
- Take a variable called level, when ever you go left, do level++ AND when ever you go right do level–.
- With the step above we have separated out the levels vertically.
- Now all we need to do the level order traversal just to ensure that we will visit the top most node at level before we visit any other node at that level.
- We will use simple queue technique for level order traversal or BFS.
- we will create a class QueuePack, this will store the objects containing node and its level.
- See the code for a better understanding.
1 2 3 4 7 8