Top View of BT

Medium

First node seen in each column

Problem

Return the top view of a binary tree: the first node seen in each column from the top.

In simple words

BFS with a horizontal distance; the first node seen in each column is visible from the top.

The idea

Run a level-order traversal tracking each node's horizontal distance and record a column only the first time it is met. BFS guarantees that first sighting is the shallowest node in that column, which is exactly what is visible from above.

The trick

Use BFS, not DFS — DFS can reach a deeper node in a column first.
Record only when the column is not already present.

←→stepspaceplay

1/5

Optimal

timeO(n)spaceO(n)

Fix the level width up front.

1const q = [root], out = [];2while (q.length) {3  const level = [];4  for (let n = q.length; n > 0; n--) {5    const node = q.shift();6    level.push(node.val);7    if (node.left) q.push(node.left);8    if (node.right) q.push(node.right);9  }10  out.push(level);11}

Input

nodes: 6, 5 edges

Memory

levels: —

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: tree = [1,2,3,4,5,6,7]
Output:: [4, 2, 1, 3, 7]
Explanation:: Looking down, you see the top node in each column.

Example 2

Input:: tree = [1,2,3]
Output:: [2, 1, 3]
Explanation:: Columns -1,0,1 → 2,1,3.

Example 3

Input:: tree = [1]
Output:: [1]
Explanation:: Just the root.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.