Day 19: Trees — BFS & DFS

DAY 19 / 30 · WEEK 3

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)

BFS (level order): visit every node at the current depth before moving to the next

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset🔀 Shuffle

Interactive visualization: DFS (preorder, iterative stack)

DFS (preorder, iterative stack): go deep before going wide

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset🔀 Shuffle

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

Step	Dequeue	Children enqueued	Queue after	Visited so far
1	1	2, 3	[2, 3]	[1]
2	2	4, 5	[3, 4, 5]	[1, 2]
3	3	6, 7	[4, 5, 6, 7]	[1, 2, 3]
4	4	— (leaf)	[5, 6, 7]	[1, 2, 3, 4]
5	5	— (leaf)	[6, 7]	[1, 2, 3, 4, 5]
6	6	— (leaf)	[7]	[1, 2, 3, 4, 5, 6]
7	7	— (leaf)	[]	[1, 2, 3, 4, 5, 6, 7]

Dry run: dfs(root) on the same tree

Step	Pop	Children pushed (right, left)	Stack after (bottom→top)	Visited so far
1	1	3, 2	[3, 2]	[1]
2	2	5, 4	[3, 5, 4]	[1, 2]
3	4	— (leaf)	[3, 5]	[1, 2, 4]
4	5	— (leaf)	[3]	[1, 2, 4, 5]
5	3	7, 6	[7, 6]	[1, 2, 4, 5, 3]
6	6	— (leaf)	[7]	[1, 2, 4, 5, 3, 6]
7	7	— (leaf)	[]	[1, 2, 4, 5, 3, 6, 7]

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

Traversal	Time	Space	Why
BFS (queue)	O(n)	O(w)	Every node is visited exactly once (O(n) time). The queue’s peak size is the widest level of the tree — w — since an entire level can sit in the queue at once.
DFS (stack or recursion)	O(n)	O(h)	Every node is visited exactly once (O(n) time). The stack’s (or call stack’s) peak size is the tree’s height — h — since it only ever holds one path from root to the current node.

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

1. Invert Binary Tree (Easy — LeetCode: Invert Binary Tree)

   • Given the root of a binary tree, swap every node’s left and right children, all the way down, and return the new root.
   • Hint: Think about what changes at every single node, not just the root — the recursive shape you need already appears in today’s traversal functions (do something to a node, then recurse into both children).
   • Solution:

     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;
     }

2. Maximum Depth of Binary Tree (Easy — LeetCode: Maximum Depth of Binary Tree)

   • Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from the root down to the farthest leaf.
   • Hint: You don’t need BFS or DFS by name here — think recursively about what “depth” means in terms of a node’s two subtrees’ own depths.
   • Solution:

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

3. Binary Tree Level Order Traversal (Medium — LeetCode: Binary Tree Level Order Traversal)

   • Given the root of a binary tree, return the values of its nodes grouped level by level (an array of arrays, one per depth) — today’s BFS, applied directly.
   • Hint: This is today’s BFS almost unchanged — the only new idea is capturing “how many nodes are currently in the queue” right before the inner loop starts, so you know exactly where one level ends and the next begins.
   • Solution:

     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

Quiz: 1. Which data structure does BFS use to control visiting order?

A FIFO queue

A FIFO queue ensures the first node discovered is the first one expanded — that’s exactly what makes BFS process one full level before moving to the next.

Quiz: 2. Which data structure does today’s iterative DFS use?

A LIFO stack

A LIFO stack — the most recently pushed node is the next one popped and visited, which is what drives DFS to go deep before it goes wide.

Quiz: 3. On today’s tree, why does BFS’s visit order come out as exactly 1, 2, 3, 4, 5, 6, 7 — the same as the node labels?

The tree’s values were deliberately assigned in level order for this lesson — it’s a labeling choice, not a general BFS property

BFS visits by structural level, not by value — the order only looks like ascending numbers here because the nodes were deliberately labeled 1-7 in level order for this lesson. Shuffle the values and BFS still visits root, then both children, then all four grandchildren, just with different numbers attached.

Quiz: 4. On a complete binary tree with about 1,000 nodes (roughly 10 levels deep, so the widest level holds close to 500 nodes), which traversal’s extra space blows up the most?

BFS — its queue must hold the entire widest level at once

BFS’s queue must hold the entire widest level at once — close to 500 nodes here — while DFS’s stack only ever holds O(h), around 10 frames, since a complete binary tree this size is only about 10 levels deep.

Quiz: 5. What should bfs(null) (or dfs(null)) return, and why does it matter?

An empty array — every traversal must guard for a null root before touching .val

An empty tree is a completely valid input — skipping the null check causes a crash the instant the queue or stack tries to read node.val off a null root.