Top View of Binary Tree

Top View of Binary Tree asks what you would see if you floated directly above the tree and looked straight down. It is a clean lesson in pairing a level-order BFS with a small piece of bookkeeping — a horizontal distance — to decide which nodes are visible.

The slow way first

You could try to reason column by column, walking down each vertical line and keeping the first node — but a tree is not laid out in columns, so there is no easy way to "walk a column." You would end up doing a full traversal anyway, then sorting and grouping by position, which is fiddly and easy to get wrong.

The better question: can I give each node a coordinate that says which column it belongs to, then let a single traversal fill in the answer? Yes — that coordinate is the horizontal distance.

The idea: horizontal distance plus first-come-first-served

Give the root horizontal distance hd = 0. Whenever you move to a left child, subtract 1; to a right child, add 1. Nodes that end up with the same hd sit in the same vertical column.

Now run a BFS (level order). Because BFS visits shallower nodes before deeper ones, the first node you reach at any given hd is the highest node in that column — exactly the one visible from above. Keep a map hd -> value and only write when the hd is new.

The key insight: BFS order guarantees top-most-first, so a simple "write only if this hd is new" rule is all the bookkeeping you need.

Walk through it

Step through the animation. Each node shows its hd tag. BFS pops nodes level by level; the top map fills as new columns appear. When 5 and 6 come up — both hd 0 — the column is already owned by the root 1, so they are hidden behind it and skipped. At the end, reading the map by hd from left to right gives the answer.

Pseudocode

if tree is empty: return []
top = empty map         # horizontal distance -> first value seen
queue = [(root, hd = 0)]
while queue is not empty:
    (node, hd) = pop front of queue
    if hd is not already a key in top:
        top[hd] = node value          # first node at this column
    if node has left child:  enqueue (left,  hd - 1)
    if node has right child: enqueue (right, hd + 1)
return values of top sorted by hd, left to right

The Python solution

from collections import deque
 
def top_view(root):
    if not root:
        return []
    top = {}                       # hd -> first value seen
    queue = deque([(root, 0)])     # (node, hd)
    while queue:
        node, hd = queue.popleft()
        if hd not in top:          # first node at this hd
            top[hd] = node.val
        if node.left:  queue.append((node.left, hd - 1))
        if node.right: queue.append((node.right, hd + 1))
    return [top[hd] for hd in sorted(top)]

• top maps a horizontal distance → the first value seen at that distance.
• queue holds (node, hd) pairs; we seed it with the root at hd = 0.
• queue.popleft() is what makes this BFS — front of the queue, so shallower nodes come out first.
• if hd not in top: is the whole trick — we record a column only the first time we reach it, and BFS guarantees that first time is the top-most node.
• Children inherit hd - 1 (left) and hd + 1 (right), so each enqueue places the child in the right column.
• The final line reads the map in hd order, giving the top view left to right.

Complexity

Each node is visited exactly once, so the traversal is O(n). The final sort touches one entry per column. The map and queue each hold up to O(n) entries.

When this pattern shows up

Practice