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.
Think of it this way, @marcotuliorr. Imagine if that '3' node had three consecutive children "7 - 8 - 9" (each node is the left child of its parent.) Would that branch cross over the long "4 - 5 - 6" branch and make the top-down view of the tree "9 - 2 - 1 - 3 - 6"? Of course not!
Every node's child must retain the positional properties of its parent, I.E. if 2 is to the left of 1, then 4 and 5 must also be to the left of 1. If 5 is to the left of 1, 6 must be to the left of 1 as well, etc. There's no way a branch not on the leftmost or rightmost path could be visible from the top down.
I think that link is wrong. In a binary tree, once you go left, all descendants of that child are by definition left of that parent. To get an accurate spatial representation you have to expand your tree so that the bottom level will fit if it is full. They say:
But all nodes 'left' of the 1 should be drawn to the left of the 1. If the tree's bottom level was full it would have 16 nodes and it should be drawn that way. If you add a node '7' left of '3' using this representation, it would overlap with the '4'.
Tree : Top View
You are viewing a single comment's thread. Return to all comments →
I think Faland is right. This link correctly defines tree top view: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
Think of it this way, @marcotuliorr. Imagine if that '3' node had three consecutive children "7 - 8 - 9" (each node is the left child of its parent.) Would that branch cross over the long "4 - 5 - 6" branch and make the top-down view of the tree "9 - 2 - 1 - 3 - 6"? Of course not!
Every node's child must retain the positional properties of its parent, I.E. if 2 is to the left of 1, then 4 and 5 must also be to the left of 1. If 5 is to the left of 1, 6 must be to the left of 1 as well, etc. There's no way a branch not on the leftmost or rightmost path could be visible from the top down.
That makes sense. "For all nodes, everything down the right branch is to the node's right; Everything down the left branch is to the node's left."
It makes sense if you think of it in the context of a binary search tree, and left and right as less than and greater than.
I think that link is wrong. In a binary tree, once you go left, all descendants of that child are by definition left of that parent. To get an accurate spatial representation you have to expand your tree so that the bottom level will fit if it is full. They say:
But all nodes 'left' of the 1 should be drawn to the left of the 1. If the tree's bottom level was full it would have 16 nodes and it should be drawn that way. If you add a node '7' left of '3' using this representation, it would overlap with the '4'.