DSA Tracker

Visualize

Top View of Binary Tree

BFS by column — first arrival at a column wins

time O(n log n) — sorting the columnsspace O(n) — the column map and the queue

Give every node a column: the root is column 0, a left step is column-1, a right step is column+1. The node visible from above in a column is whichever one sits closest to the top — and BFS visits nodes in top-to-bottom row order, so the very FIRST time a column is reached in BFS, that node is guaranteed to be the shallowest one there. A hash map from column to value, only ever written on first arrival, is the whole algorithm.

Details

Animated on: root = [1,2,3,4,5,6,7] — return the values visible looking down from above: exactly one value per vertical column, the shallowest node in it. Expected: [4,2,1,3,7].

Problem:Top View of Binary TreeMedium

BFS by column — first arrival at a column wins

step 1 / 9

4
2
5
1
6
3
7

Call stack

queue: [1(c=0)]top view so far: {(empty)}

Start BFS at the root, 1, column 0. A node's column is fixed the moment it is enqueued — left goes col-1, right goes col+1 — and never changes afterward.

Pseudocode
1FUNCTION topView(root):
2  IF root = null: RETURN []
3  colMap <- empty map
4  queue <- [(root, 0)]
5  WHILE queue is not empty:
6    (node, col) <- DEQUEUE(queue)
7    IF col NOT IN colMap:
8      colMap[col] <- node.val
9    IF node.left != null: ENQUEUE(queue, (node.left, col - 1))
10    IF node.right != null: ENQUEUE(queue, (node.right, col + 1))
11  RETURN colMap values ordered by col ascending

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. Start BFS at the root, 1, column 0. A node's column is fixed the moment it is enqueued — left goes col-1, right goes col+1 — and never changes afterward.
  2. Dequeue 1 at column 0 — column 0 hasn't been claimed yet, so 1 becomes the top-view value there. Enqueue 2 at column -1 and 3 at column 1.
  3. Dequeue 2 at column -1 — column -1 hasn't been claimed yet, so 2 becomes the top-view value there. Enqueue 4 at column -2 and 5 at column 0.
  4. Dequeue 3 at column 1 — column 1 hasn't been claimed yet, so 3 becomes the top-view value there. Enqueue 6 at column 0 and 7 at column 2.
  5. Dequeue 4 at column -2 — column -2 hasn't been claimed yet, so 4 becomes the top-view value there. 4 is a leaf — nothing to enqueue.
  6. Dequeue 5 at column 0 — column 0 is already claimed by 1 (first arrival wins), so 5 is hidden beneath it and skipped. 5 is a leaf — nothing to enqueue.
  7. Dequeue 6 at column 0 — column 0 is already claimed by 1 (first arrival wins), so 6 is hidden beneath it and skipped. 6 is a leaf — nothing to enqueue.
  8. Dequeue 7 at column 2 — column 2 hasn't been claimed yet, so 7 becomes the top-view value there. 7 is a leaf — nothing to enqueue.
  9. Queue empty. Reading columns left to right (-2 to 2): 4, 2, 1, 3, 7 — that is the top view.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Top View of Binary Tree in the editorAll Binary Trees problemsBack to roadmap