GeeksforGeeks Medium

Top View of Binary Tree

Values visible from above: for each column, the first node in level order.

treebfshash-table

02

Intuition

Mirror of bottom view: BFS with column indices, but a column is claimed by the FIRST node that reaches it — later (deeper) nodes in that column are hidden underneath.

How to spot this pattern

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.

03

Approach

1

BFS with columns

Queue of (node, col); left −1, right +1. BFS guarantees shallower nodes come first.

2

First write wins

Only set map[col] if the key is new. DFS would break this — depth order isn't guaranteed.

3

Sorted columns out

Emit values by ascending column.

04

Solution & live demo

▶1from collections import deque
▶2 
▶3def top_view(root):
▶4    if not root: return []
▶5    seen = {}
▶6    q = deque([(root, 0)])
▶7    while q:
▶8        node, c = q.popleft()
▶9        if c not in seen:                 # first write per column wins
▶10            seen[c] = node.val
▶11        if node.left: q.append((node.left, c - 1))
▶12        if node.right: q.append((node.right, c + 1))
▶13    return [seen[c] for c in sorted(seen)]

05

Common pitfalls

Using DFS instead of BFS

✗ Wrong

def dfs(node, c, depth):
    if c not in seen: seen[c] = node.val

✓ Right

q = deque([(root, 0)])
while q:
    node, c = q.popleft()
    if c not in seen: seen[c] = node.val

DFS 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

✗ Wrong

seen[c] = node.val

✓ Right

if c not in seen:
    seen[c] = node.val

Later 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

✗ Wrong

return list(seen.values())

✓ Right

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.

06

Edge cases

Deep node in an unclaimed column

It IS visible (nothing above it) — first-write logic includes it correctly.

Same level, same column

Left-to-right BFS order decides — matches GFG convention.

07

Complexity

Time

O(n log n)

Space

O(n)

BFS + column sort.