DAY 19 / 30 · WEEK 3

Trees — BFS & DFS

Goal of the day

• Build a binary tree from a simple TreeNode class (val, left, right) — the same three-field shape as Day 15's linked-list Node, just with two pointers instead of one.
• Traverse it two genuinely different ways on the exact same tree: BFS (level order, using a queue) and DFS (as deep as possible before backtracking, using a stack or recursion) — and see the visit orders actually diverge.
• Know which one to reach for and why: BFS for shortest-path problems and level-by-level processing, DFS for full-path exploration and the natural recursive shape most tree problems already have — and how each traversal's extra memory use depends on the tree's shape (width vs. height).

Concept

A tree is a hierarchy: one root node at the top, connected by edges down to child nodes, each of which can have children of its own. Unlike Day 15's linked list — a straight chain, one .next per node — a tree branches. A binary tree puts one specific limit on that branching: every node has at most two children, conventionally called left and right.

Think of a company org chart deliberately kept flat: every manager (a node) has at most two direct reports (its left and right children) — no more. The CEO is the root; anyone with no direct reports is a leaf. A family tree drawn top-down works the same way once you cap each person at two "children" slots — same shape, different labels.

Picture exploring a multi-floor building maze-style, breadth-first: you fully explore every room on floor 1 before taking a single step onto floor 2, then fully explore floor 2 before floor 3. That's BFS (breadth-first search) — visit every node at the current depth before moving to the next depth, using a queue (first discovered, first explored) to enforce that order.

Now picture the opposite strategy: pick a corridor and follow it all the way to its dead end before backtracking to try the next one. That's DFS (depth-first search) — go as deep as possible down one branch before backtracking, using a stack (most recently discovered, next explored) or plain recursion (the call stack does the same job for free) to enforce that order.

Diagram: anatomy of a binary tree

Diagram: BFS order vs. DFS order on the same tree

Interactive visualization: BFS (level order)

Interactive visualization: DFS (preorder, iterative stack)

The code: BFS with a queue, DFS with a stack

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function bfs(root) {
  const result = [];
  if (!root) return result;          // empty tree — nothing to visit
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();       // FIFO: take the OLDEST discovered node
    result.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

function dfs(root) {
  const result = [];
  if (!root) return result;          // empty tree — nothing to visit
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();         // LIFO: take the NEWEST discovered node
    result.push(node.val);
    if (node.right) stack.push(node.right); // push right first...
    if (node.left) stack.push(node.left);   // ...so left is popped (visited) first
  }
  return result;
}

Line by line:

• TreeNode mirrors Day 15's Node class — a value plus pointers to what comes next — except a tree node has two "next" pointers instead of one, because a tree branches instead of chaining.
• Both functions guard the empty tree first (if (!root) return result;) — skip this and the very first line inside the loop tries to read .val off null.
• bfs uses queue.shift() to remove from the front of the array — first discovered, first visited (FIFO). Each visited node's children get pushed to the back, so the whole current level finishes before the next level starts.
• dfs uses stack.pop() to remove from the end of the array — most recently discovered, next visited (LIFO). Pushing right before left is the one deliberate trick: it puts left on top of the stack, so left is the next one popped — matching the natural "visit node, then left subtree, then right subtree" preorder shape.
• Both loops are otherwise structurally identical — same guard, same "take one, record it, push its children" shape. The only difference between BFS and DFS here is shift() vs. pop() and which end children get pushed to. That's the whole trick: same skeleton, different data structure, opposite visiting order.

Dry run: bfs(root) on the tree above

Dry run: dfs(root) on the same tree

Same tree, same starting node — two entirely different orders. BFS finishes an entire level before starting the next; DFS drains the whole left branch (down to leaves 4 and 5) before it ever backtracks to node 3.

Complexity

n = total nodes, w = the widest level's node count, h = the tree's height. These are not interchangeable: on a balanced tree, w ≈ n/2 and h ≈ log n, so DFS uses far less space. On a wide-but-shallow tree (many nodes, few levels), w can approach n while h stays tiny — DFS wins big. On a narrow-but-skewed tree (essentially a linked list), h can approach n while w stays tiny — now BFS's queue barely grows, and DFS is the one paying O(n) space. The tree's shape decides which one is cheaper, not the algorithm name.

Interview corner

• When would you choose BFS over DFS, and vice versa? BFS is the right call whenever you need shortest-path-style behavior in an unweighted structure, or you need to process a tree strictly level by level (print every node at depth 2, find the minimum depth to a target, etc). DFS is the natural fit when you need to explore a full root-to-leaf path before moving on (path-sum problems, structural validation top to bottom), and it's usually the more natural recursive formulation of a tree problem.
  ↳ Common follow-up: "What if the tree is very deep but narrow — a completely skewed, linked-list-shaped tree?" Then DFS's stack grows to O(n), the same order BFS's queue would hit if the tree were wide and shallow instead — "DFS uses less memory" is only true relative to a specific tree shape, not universally.
• Why does BFS specifically need a FIFO queue, and DFS a LIFO stack? The two traversals are defined entirely by their processing order. Level-by-level order requires fully processing everything discovered so far before moving to the next batch — a queue's first-in-first-out order does exactly that. Going as deep as possible before backtracking requires processing what was most recently discovered first — a stack's last-in-first-out order does exactly that. Swap the data structure in the identical loop skeleton above and you get the other traversal's order — no other code change needed.
• What's the classic bug when writing bfs()/dfs() for a real tree?
  ⚠ Trap: forgetting to guard the empty-tree case (root === null). Both loop-based traversals shown today start with if (!root) return result; — skip it and queue = [root] / stack = [root] seeds the loop with null, and the very first iteration crashes trying to read null.val.
• Is preorder the only "flavor" of DFS? No — preorder, inorder, and postorder are all DFS; they just differ in when a node's own value is recorded relative to recursing into its children (before both, between them, or after both). Today's animation shows preorder (visit node, then left, then right) because it's the most intuitive to trace by eye, but the same stack/recursion mechanics power all three — only the position of one line (result.push(node.val)) moves.
• On a wide-but-shallow tree vs. a narrow-but-deep (skewed) tree, how does each traversal's extra space actually behave? BFS's queue holds, at its peak, every node on the widest level (w). DFS's stack (or recursion depth) holds, at its peak, one frame per level from root to the current node (h). On a wide, shallow tree, w is huge and h is tiny — DFS wins on space. On a narrow, deep (skewed) tree, h is huge (up to n) and w is tiny — now BFS barely grows, and DFS is the one using O(n) space. Neither is "just better"; the shape of the tree decides which structure blows up.

How to talk through it out loud: name the data structure before writing a single line — "BFS needs a queue because I want first-in-first-out, level-by-level order; DFS needs a stack, or recursion, because I want last-in-first-out, depth-first order." Then narrate the empty-tree guard out loud before touching .val — "first, what happens if root is null?" Interviewers watching a tree-traversal solution are listening for exactly these two things: do you reach for the right structure on purpose, not by memorized template, and do you handle the empty case before you ever dereference a node.

Practice problems

function invertTree(root) {
  if (!root) return null;
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
}

function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

function levelOrder(root) {
  const result = [];
  if (!root) return result;
  const queue = [root];
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Quiz