Looking from above
List the nodes visible from above - the first node reached in each vertical column - by combining the column numbers with the level order walk. About 14 minutes.
The first node in each column
Imagine looking down at the tree from above. In each vertical column, the node nearest the top hides the ones below it. So you see one node per column: the one with the smallest depth.
Give each node its column number, as in the last step. Walk the tree by level, so you meet shallower nodes first, and record a node's value the first time its column appears.
bottom[col] = node.val # later ones overwrite
- view
- col 0: 4
4 is in column 0 and is first there. Visible: 4.
Order of the answer
Level order visits a whole level before the next, and left before right within a level. If two nodes share a column and a level, the left one is met first and wins. That is a fixed rule, so the answer is the same every time.
At the end, list the recorded values from the leftmost column to the rightmost. A map keyed by column, with its keys sorted, does the job.
left_to_right = sorted(top)
A node in column 3 is met, and column 3 already has an entry. What do you do?
- AIgnore it, since the earlier node is higher or further left
- BReplace the entry
- CAdd it as another entry
Show the answer
Ignore it, since the earlier node is higher or further left. Level order meets nodes from the top down, so the first one is on top.
Top view of a binary tree
Given the root of a binary tree, assign the root to column 0, each left child to the column one less than its parent's, and each right child to the column one more. Looking down from above, a node is visible if no other node in the same column is higher; if two nodes in a column are on the same level, the one further to the left (reached first in a left-to-right level walk) is visible. Return the visible nodes' values from the leftmost column to the rightmost.
root = [1, 2, 3, 4, null, null, 5, null, 6] → [4, 2, 1, 3, 5]
0 ≤ number of nodes ≤ 10,000 · 0 ≤ node.val ≤ 100,000