Tree Traversal in JS

The plain-language idea

A tree is just nested nodes, each with children — the DOM, nested comments, a folder structure, a JSON object with children arrays. Visiting every node in some order is "traversal," and there are exactly two strategies: depth-first (go as deep as possible down one branch before backtracking) and breadth-first (visit everything at the current level before going deeper).

Depth-first splits further by when you process a node relative to its children: pre-order (visit the node, then its children), in-order (visit left child, node, right child — only meaningful for binary trees), and post-order (visit all children, then the node). Breadth-first only has one natural order: level by level, left to right.

The mechanism matters as much as the order. Recursion gives you depth-first for free because the call stack is the stack you'd otherwise manage by hand. Breadth-first needs an explicit queue. You can also do depth-first iteratively with your own explicit stack — useful when recursion risks blowing the call stack on a very deep tree.

See it in a real thing: walking a DOM-like tree

const tree = {
  value: "body",
  children: [
    { value: "header", children: [{ value: "logo", children: [] }] },
    { value: "main", children: [
      { value: "article", children: [] },
      { value: "aside", children: [] },
    ] },
  ],
};

// Depth-first, recursive (pre-order)
function dfsRecursive(node, visit) {
  visit(node.value);
  for (const child of node.children) dfsRecursive(child, visit);
}

// Depth-first, iterative — explicit stack instead of the call stack
function dfsIterative(root, visit) {
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    visit(node.value);
    // push in reverse so the leftmost child is popped first
    for (let i = node.children.length - 1; i >= 0; i--) stack.push(node.children[i]);
  }
}

// Breadth-first — always needs an explicit queue, recursion doesn't fit
function bfs(root, visit) {
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    visit(node.value);
    queue.push(...node.children);
  }
}

dfsRecursive(tree, console.log); // body, header, logo, main, article, aside
bfs(tree, console.log);          // body, header, main, logo, article, aside

Compare the two DFS versions: dfsRecursive visits a node then immediately recurses into its first child — depth first, driven by the call stack. dfsIterative produces the same order using an array as a manual stack; note the reverse-order push, needed because pop() takes from the end, so children must go on in reverse to come off left-to-right. bfs swaps pop() for shift() and pushes all of a node's children before moving to the next node in the queue — that's what makes it expand level by level instead of branch by branch.

What people usually miss

Watch out

• "Iterative" doesn't mean "no stack." The iterative DFS still uses a stack — it's just an array you manage yourself instead of the JS engine's call stack. The traversal order is identical; only who owns the bookkeeping changes.
• Recursion depth is a real limit. A deeply nested tree (a long linked-list-shaped DOM, a deeply recursive JSON blob) can blow the call stack with recursive DFS. The iterative version with an explicit array has no such ceiling beyond available memory.
• BFS can't be written recursively in any natural way. Recursion mirrors depth-first exploration; breadth-first needs to hold "everything at this level" simultaneously, which is what a queue is for, not a call stack.

The genealogy: this is what the browser does to render your page

The DOM tree gets walked with exactly this kind of traversal — element.querySelectorAll, style computation, and the accessibility tree are all built by visiting nodes in some defined order. Event bubbling and capturing, covered in the event delegation lesson, is really just an in-order walk up and down that same tree.