Binary Tree Top/Bottom View
Draw the tree so the root sits at horizontal position 0, every left step moves one unit left and every right step one unit right. Nodes sharing a position line up in the same vertical column. The top view is the shallowest node of each column; the bottom view is the deepest. Return the chosen values ordered by column from leftmost to rightmost. An empty tree returns an empty list.
- The number of nodes is in the range [0, 100]
- -100 <= Node.val <= 100
- Columns are ordered left to right in the output
- Exactly one value per non-empty column
root = [1,2,3,4,5,6,7], top view[4,2,1,3,7]root = [1,2,3,4,5,6,7], bottom view[4,5,6,3,7]root = [1,2,3,null,4], top view[2,1,3]root = [1], top view[1]Both views group the nodes into vertical columns, then pick one node per column: the top view keeps the shallowest (what you'd see from above), the bottom view the deepest (from below).
"Column" needs defining — a tree node has no horizontal coordinate — so give it one: root = column 0, every step left is −1, every step right is +1. Nodes with the same number line up vertically, no matter how far apart in the tree.
1(0)
/ \
2(-1) 3(1)
/ \ / \
4(-2) 5(0) 6(0) 7(2)
column: -2 -1 0 1 2
top: 4 2 1 3 7 (shallowest in each column)
bottom: 4 5 6 3 7 (deepest; 5 & 6 tie in col 0 -> later one, 6)See column 0: it gathers 1, 5, and 6 — from three different parts of the tree, because a left-then-right path lands back where the root is. That mixing is the whole difficulty: you can't walk a column directly, so you can't just "go down column 0."
So collect instead of search. Visit every node and file it under its column number in a map. The only decision is what happens when a column already has an entry:
For "first filed = shallowest" to hold, we must visit shallow nodes before deep ones — which is exactly what a BFS (level-by-level) sweep gives: all of depth 0, then depth 1, and so on, so arrival order equals depth order. A depth-first walk would break it (a deep left node arrives long before a shallow right one), and the top view would pick wrong. BFS isn't stylistic here — it's what makes the tie-break sound.
if root is None: return []
col = {} # column -> chosen value
queue = deque([(root, 0)]) # each entry: a node and its column
while queue:
node, x = queue.popleft()
if is_top:
if x not in col: # first arrival = shallowest
col[x] = node.val
else:
col[x] = node.val # last arrival = deepest
if node.left: queue.append((node.left, x - 1))
if node.right: queue.append((node.right, x + 1))
return [col[x] for x in sorted(col)] # columns, leftmost firstsorted isn't optional — the map's keys are column numbers that can be negative and arrive in any order, so the output must be ordered explicitly. (If that O(K log K) matters, track the smallest and largest column during the walk and read the map from min to max — O(K), since every column between two occupied ones is also occupied.)Same tree as above:
visit 1 @col 0 -> col 0 empty -> keep 1
visit 2 @col -1 -> keep 2 visit 3 @col +1 -> keep 3
visit 4 @col -2 -> keep 4
visit 5 @col 0 -> taken (1 shallower) -> skip
visit 6 @col 0 -> taken -> skip
visit 7 @col +2 -> keep 7
sort columns -2..2 -> [4, 2, 1, 3, 7]Bottom view on the same tree overwrites instead: column 0 goes 1 → 5 → 6, leaving 6 (the later of the two deepest), giving [4, 5, 6, 3, 7]. The queue's left-to-right order is what makes 6 beat 5 — worth flagging to an interviewer as the tie convention.
Each node enqueued and dequeued once: O(N) walk, plus O(K log K) to sort columns; O(N) space. The reusable skeleton is coordinate, collect, resolve: give each node a coordinate that captures the geometry the question cares about, group by it, then apply a tie-break inside each group.
Vertical Projection
Toggle between Top and Bottom views
Column projection
Project every node onto a horizontal x-axis (HD).