Given the root of a binary tree, return its top view — the set of nodes visible when the tree is viewed from directly above, ordered from left to right.
Assign each node a horizontal distance: the root is 0, a left child is one less than its parent, a right child one more. For each horizontal distance, the visible node is the topmost one (closest to the root). If two nodes share a horizontal distance at the same depth, the one reached earlier in a top-down, left-to-right sweep is taken.
The tree is given in level-order (breadth-first), using null for missing children.
Input: root = [1, 2, 3, null, 4, 5, 6] Output: [2, 1, 3, 6] Columns by horizontal distance: -1 -> 2, 0 -> 1 (root), 1 -> 3, 2 -> 6.
Input: root = [1, 2, 3] Output: [2, 1, 3] Left child at hd -1, root at hd 0, right child at hd 1.
- The number of nodes is in the range [0, 10^4] - 1 <= Node.val <= 10^5
Give every node a horizontal distance (root 0, left −1, right +1). Two nodes in the same vertical column share a horizontal distance; from the top you only see the topmost one. A level-order BFS visits nodes top-down, so the first node seen at each horizontal distance is exactly the visible one. Collect one value per column, then output them ordered by horizontal distance.
“What decides which node in a column is visible?”
The topmost — smallest depth; BFS's first arrival at that column.
“What order is the output?”
By horizontal distance, left (most negative) to right (most positive).
I assign each node a horizontal distance and run a level-order BFS.
The first node I dequeue for each horizontal distance is the topmost in that column, so I record it and finally sort by horizontal distance.
Worked example — tree [1, 2, 3, null, 4, 5, 6]
1(0)
/ \
2(-1) 3(1)
\ / \
4(0)5(0)6(2)
hd -1: 2 hd 0: 1 (root, topmost) hd 1: 3 hd 2: 6
result: [2, 1, 3, 6]
Nodes sharing an hd are vertically stacked; the top view picks one per column.
Level-order visits shallower nodes first, so the first node dequeued at each hd is the one you see.
A naive DFS can reach a deeper node in a column before a shallower one; you'd have to compare depths. BFS makes 'first seen = topmost' automatic.
| DFS tracking depth | BFS first-per-column | |
|---|---|---|
| Idea | Keep the smallest-depth node per hd | First node dequeued per hd is topmost |
| Time | O(n log n) | O(n log n) |
| Space | O(n) | O(n) |
Both sort by hd at the end; BFS needs no depth comparison. Full code is in the Approaches selector below.
Key takeaway
Tag nodes with a horizontal distance, BFS top-down, and keep the first node seen per column — that's the topmost. Output ordered by horizontal distance. O(n log n) for the final sort.
bfs with (node, hd):
if hd unseen: seen[hd] = node.val
enqueue (left, hd-1), (right, hd+1)
output seen[hd] for hd in sorted order