We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
@alex_mistery, I understand what you are saying, however, in my experience, top-view of a binary tree is determined by the combination of Level-Order-Traversal and Vertical-Order-Traversal, in other words, you determine all the nodes that are in the same Vertical-Order but only choose the node in each Order that first appears in the Level-Order list. So when doing this, you get the following...
Level_Order=[1,2,3,4,5,6,7,8]
Vertical-Orders are the following (0 is root position, all others are delta from root)
Since 4, 2, 7, 8 are alone in there set, we don't have to refer to the level order choose. In the 0 and 1 Distances from the root, we have [1,5] and [3,6]. 1 occurs first in Level_order over 5, so we choose 1. 3 occurs first in Level_order over 6, so we choose 3. So after eliminating 5 and 6, going from left-right, we get...
4,2,1,3,7,8
This is the algo used in Geeks for Geeks and is widely used in all documentation of top-view I've seen. So, @Faland is correct in this respect. Intuitively, the alternative where someone only see the higher levels in the top-view without compensating for vertical displacement doesn't make any sense. Think about how a pyramid works. If I were to take @alex_mistery's interpretation, I shouldn't be able to see the outerbricks on the base of a pyramid if I was looking down from the top no matter how far away from the center those bricks were.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tree : Top View
You are viewing a single comment's thread. Return to all comments →
@alex_mistery, I understand what you are saying, however, in my experience, top-view of a binary tree is determined by the combination of Level-Order-Traversal and Vertical-Order-Traversal, in other words, you determine all the nodes that are in the same Vertical-Order but only choose the node in each Order that first appears in the Level-Order list. So when doing this, you get the following...
Vertical-Orders are the following (0 is root position, all others are delta from root)
Since 4, 2, 7, 8 are alone in there set, we don't have to refer to the level order choose. In the 0 and 1 Distances from the root, we have [1,5] and [3,6]. 1 occurs first in Level_order over 5, so we choose 1. 3 occurs first in Level_order over 6, so we choose 3. So after eliminating 5 and 6, going from left-right, we get...
This is the algo used in Geeks for Geeks and is widely used in all documentation of top-view I've seen. So, @Faland is correct in this respect. Intuitively, the alternative where someone only see the higher levels in the top-view without compensating for vertical displacement doesn't make any sense. Think about how a pyramid works. If I were to take @alex_mistery's interpretation, I shouldn't be able to see the outerbricks on the base of a pyramid if I was looking down from the top no matter how far away from the center those bricks were.