Bottom view of BT

Medium

Last node seen in each column

Problem

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

In simple words

BFS with horizontal distance; the last node seen in each column is what you'd see from underneath.

The idea

The same level-order walk with horizontal distances, but overwrite the entry for a column every time. The final value per column is the deepest node there, which is what you see from below.

The trick

Always overwrite — the opposite of the top view.
Later levels win, which is why BFS ordering matters.

←→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 = [20,8,22,5,3,4,25]
Output:: [5, 8, 4, 22, 25]
Explanation:: The last node in each column shows from below.

Example 2

Input:: tree = [1,2,3]
Output:: [2, 1, 3]
Explanation:: 2,1,3.

Example 3

Input:: tree = [1]
Output:: [1]
Explanation:: Root only.

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

Finished the walkthrough? Add it to your streak.