Skip to lesson
Exit
Applied Coding & Editor Primitives1 / 3

1 min lesson

Tree traversals as outline problems

Use "A code outline is a tree and rendering it is a traversal" to say what you would do next.

Step 1 of 3

Tree traversals as outline problemstop view, level order

Reframe these the way the editor uses them: a code outline is a tree and rendering it is a traversal. The top view of a binary tree - the nodes visible from above - is a BFS where you track each node's horizontal distance from the root and keep the first node seen at each distance.

Learn more

Full explanation

Top view: BFS, first node at each horizontal distance wins

Top view: BFS, first node at each horizontal distance wins.ts
interface TreeNode { val: number; left?: TreeNode; right?: TreeNode; }

function topView(root?: TreeNode): number[] {
  if (!root) return [];
  const firstAtHd = new Map<number, number>();   // horizontalDist -> value
  const queue: Array<{ node: TreeNode; hd: number }> = [{ node: root, hd: 0 }];
  let minHd = 0, maxHd = 0;

  while (queue.length) {
    const { node, hd } = queue.shift()!;
    if (!firstAtHd.has(hd)) firstAtHd.set(hd, node.val);  // BFS => topmost first
    minHd = Math.min(minHd, hd);
    maxHd = Math.max(maxHd, hd);
    if (node.left) queue.push({ node: node.left, hd: hd - 1 });
    if (node.right) queue.push({ node: node.right, hd: hd + 1 });
  }

  const out: number[] = [];
  for (let hd = minHd; hd <= maxHd; hd++) out.push(firstAtHd.get(hd)!);
  return out;
}
BFS, not DFS, for top view

A DFS can reach a node at a given horizontal distance before a shallower node at the same distance, giving you the wrong answer. BFS guarantees you see the topmost node at each distance first. State this reason aloud - choosing the traversal because of the invariant is the signal.