Tree Traversal: BFS and DFS

Every tree problem that isn't a simple search boils down to one question: in what order do you visit the nodes? This lesson covers the two fundamental answers — breadth-first and depth-first — and, more importantly, how to recognize which one a given problem actually needs.

Depth-first search (DFS): dive, then backtrack

DFS goes as deep as possible down one branch before backing up to try the next one. The natural implementation is recursive, because recursion's call stack is exactly the "remember where to backtrack to" mechanism DFS needs:

function dfs(node, visit) {
  if (!node) return;
  visit(node.value);
  for (const child of node.children) {
    dfs(child, visit);
  }
}

For a tree shaped like root → [A → [A1, A2], B → [B1]], this visits root, A, A1, A2, B, B1 — it fully exhausts A's entire subtree before ever looking at B.

An iterative version replaces the call stack with an explicit array stack — exactly the technique from the recursion-vs-iteration lesson:

function dfsIterative(root, visit) {
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    visit(node.value);
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]); // reverse order so leftmost child pops first
    }
  }
}

Breadth-first search (BFS): level by level

BFS visits every node at the current depth before moving to the next depth. It cannot be written recursively in the natural way DFS can — it needs a queue (first-in-first-out), not a stack:

function bfs(root, visit) {
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift(); // remove from the FRONT
    visit(node.value);
    for (const child of node.children) {
      queue.push(child); // add to the BACK
    }
  }
}

For the same tree as above, this visits root, A, B, A1, A2, B1 — everything at depth 1 (A, B) before anything at depth 2. That single difference — stack (LIFO) for DFS, queue (FIFO) for BFS — is the entire mechanical distinction between the two, and it's worth tracing by hand once until it's automatic.

(A production queue.shift() has a real cost worth flagging: shifting the front of a JS array is O(n), because every remaining element shifts down an index. For large queues, a proper ring-buffer-backed queue avoids this — but for typical tree sizes in frontend code, .shift() is a fine, readable default.)

Choosing between them: the question that decides it

Use BFS when you need the shortest path (in edges) from the root, or you specifically care about "everything at this depth." BFS explores in strictly increasing distance from the root — everything at distance 1 before anything at distance 2 — so the very first time it reaches a target node, that's guaranteed to be via the shortest possible path. DFS has no such guarantee: it might reach the target only after a long, unrelated detour down a different branch first.

Use DFS when you need to explore a whole branch's implications before moving on, or the problem is naturally recursive — validating a nested structure, computing something that depends on a subtree's full result (size, sum, max depth) before combining it with siblings. DFS's recursive form usually matches the natural recursive definition of the problem itself.

The three flavors of DFS, briefly

When DFS specifically visits binary trees, three orderings get names based on when the current node itself is processed relative to its children:

• Preorder — node, then children (visit(node); recurse(left); recurse(right);)
• Postorder — children, then node (recurse(left); recurse(right); visit(node);)
• In-order — left child, node, right child — specific to binary trees, and notably, running in-order traversal on a binary search tree visits every value in fully sorted order, for free, as a direct consequence of the BST ordering property from the last lesson.

What to remember

• DFS uses a stack (recursion's call stack, or an explicit one) and dives depth-first; BFS uses a queue and expands level by level. That single data structure choice is the entire mechanical difference.
• Both are O(n) time for n nodes — the meaningful difference is auxiliary space, bounded by the tree's height for DFS and by its maximum width for BFS, which depends entirely on the tree's actual shape.
• BFS guarantees the first time it reaches a target is via the shortest path in edges from the root — reach for it specifically when "shortest path" or "everything at this depth" is the question.
• Preorder, postorder, and in-order are DFS orderings distinguished by when the current node is processed relative to its children; in-order on a BST visits values in fully sorted order.