Top View of Binary Tree
Top View of Binary Tree: values visible from above: for each column, the first node in level order.
- 1 <= number of nodes <= 10⁵
- -10⁹ <= node value <= 10⁹
- Ties in a column are resolved by level order, first wins
Intuition
The top view of binary tree is what you would see looking straight down at it from above: some nodes are visible, and others are hidden underneath the ones above them. To turn that picture into an algorithm you need a way to say when one node is "above" another, and the answer is to give every node a horizontal coordinate. Assign the root column 0. Every time you move to a left child the column decreases by one, and every right child increases it by one. Nodes that share a column are stacked vertically in the drawing, which means only one of them is visible from above — the shallowest one. So the question becomes: for each column, which node reaches it first? That is precisely what a breadth-first traversal answers, because BFS visits the tree level by level and therefore always reaches shallower nodes before deeper ones. Combine that with a single rule: - Write a column's value only if that column has not been claimed yet. First write wins, and BFS makes the first write the topmost node automatically. This is where depth-first search would quietly produce the wrong answer: DFS dives to the bottom of one branch before exploring its sibling, so it can easily claim a column with a deep node before a shallower node in the same column has been visited. The traversal order is not an implementation detail here — it is what makes the algorithm correct.
Assign each node a horizontal column — left child is c - 1, right is c + 1 — and the top view is the first node seen in each column. BFS is what makes "first" mean "highest", because it visits strictly by depth. Column indexing solves bottom view, vertical order, and top view alike; only the selection rule changes.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n log n) time and O(n) space.
Give every node a horizontal column
The root sits at column 0. Moving to a left child subtracts one, moving right adds one. Two nodes with the same column are drawn one above the other, and that shared coordinate is what lets you reason about which one hides the other.
Traverse breadth-first, carrying the column along
Use a queue holding (node, column) pairs, seeded with (root, 0). BFS processes the tree level by level, so every node at depth d is dequeued before any node at depth d+1. That ordering is the guarantee the rest of the algorithm relies on.
Claim each column with the first node to reach it
Keep a map from column to value. When you dequeue a node, write map[col] = node.val only if col is not already a key. Because of the BFS order, the node doing the writing is the shallowest in that column, which is exactly the one visible from above.
Enqueue the children with shifted columns
Push (node.left, col - 1) and (node.right, col + 1) when those children exist. The column arithmetic happens here, once per child, and never needs recomputing.
Emit the columns in left-to-right order
The map's keys are the visible columns, but a hash map has no order. Sort the keys ascending — from the most negative column to the most positive — and output their values. That produces the view as it would actually be seen, scanning from left to right.
Why DFS is the wrong tool here
A depth-first traversal can reach a deep node in some column before a shallow node in the same column, and the first-write-wins rule would then record the hidden node. If you do want DFS, you must additionally store each entry's depth and overwrite when a shallower node arrives — strictly more bookkeeping for the same result.
Cost of the traversal
Every node is enqueued and dequeued once, giving O(n) work, plus O(k log k) for sorting the k distinct columns at the end. Space is O(n) for the queue and the map. Using an ordered map or tracking the minimum and maximum column instead lets you skip the sort entirely.
Solution & live demo
Common pitfalls
Using DFS instead of BFS
def dfs(node, c, depth):
if c not in seen: seen[c] = node.valq = deque([(root, 0)])
while q:
node, c = q.popleft()
if c not in seen: seen[c] = node.valDFS can reach a deep node in a fresh column before a shallower node in that same column, recording something that isn't actually on top. BFS guarantees the first arrival in any column is the highest one.
Overwriting the column on every visit
seen[c] = node.val
if c not in seen:
seen[c] = node.valLater arrivals in a column are lower in the tree, so overwriting produces the bottom view. First write per column wins.
Returning the values in insertion order
return list(seen.values())
return [seen[c] for c in sorted(seen)]
BFS discovers columns in level order, not left-to-right, so the dictionary's order isn't the visual order. Sorting by column index puts them in the order you'd actually see them.
Edge cases
It IS visible (nothing above it) — first-write logic includes it correctly.
Left-to-right BFS order decides — matches GFG convention.