Pattern visualizer

Top View of Binary Tree

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. 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]..

BFS by column — first arrival at a column wins

time O(n log n) — sorting the columnsspace O(n) — the column map and the queuestep 1 / 9

Call stack

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

line 4

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap