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.
I watched a video on Youtube giving the same explanation as you did. However, what confused me is why level order traversal should be referred? Why can't we print the first node for each horizontal distance stored in the Vertical Order traversal dictionary (which is the top node of each HD)?
FYI, there is a problem with this definition. You can have overlap of the "top" nodes. For instance, when looking "to the left", you could have a branch "poke" out that coincides with another branch. In this case both nodes would appear to be at both the same level and height. My assumption (in my solution) for a tie was the the "left-most" branch was the highest--that is the branch that originated from the "most" left position (in this case that would be how I drew it).
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.
I watched a video on Youtube giving the same explanation as you did. However, what confused me is why level order traversal should be referred? Why can't we print the first node for each horizontal distance stored in the Vertical Order traversal dictionary (which is the top node of each HD)?
FYI, there is a problem with this definition. You can have overlap of the "top" nodes. For instance, when looking "to the left", you could have a branch "poke" out that coincides with another branch. In this case both nodes would appear to be at both the same level and height. My assumption (in my solution) for a tie was the the "left-most" branch was the highest--that is the branch that originated from the "most" left position (in this case that would be how I drew it).