H

Algorithms

Tree Traversal

DFS on a binary tree — preorder, inorder, postorder are one algorithm with a visit point change.

Prereqs

The algorithm

function walk(node) {
  if (!node) return;
  visit(node);          // pre-order: act before descending
  walk(node.left);
  walk(node.right);
}

This is depth-first search on a binary tree. The call stack is the traversal state — when you recurse into node.left, the current node is frozen on the stack until you return.

Why this shape is everywhere

The recursive structure (a node that contains more nodes of the same type) appears in almost every domain in software:

  • A binary tree node contains left/right children that are also binary tree nodes.
  • An HTML element contains child elements that are also HTML elements.
  • A function call contains sub-expressions that are also expressions.
  • A directory contains subdirectories that are also directories.

The shape of the data is identical. The traversal algorithm is identical. Only the names change.

Pre-order vs post-order

When you visit a node before its children, that's pre-order. When you visit after all children are processed, that's post-order.

function walk(node) {
  // PRE-ORDER: act here to see the node before its subtree
  preVisit(node);
 
  for (const child of node.children) walk(child);
 
  // POST-ORDER: act here to see the node after its subtree is done
  postVisit(node);
}

Babel exposes both as enter and exit. Useful when a transformation needs to know what's inside a node before deciding what to do with it.

When recursion isn't enough

The call stack limits recursion depth (typically 10,000–15,000 frames in V8). For shallow trees this is fine. For deep or concurrent traversal, you need to manually maintain the stack as a data structure — which is exactly what React Fiber does.

Connections

How this links to the rest

  • Binary Tree — Tree traversal IS the binary tree visited. Preorder, inorder, postorder — all three are the same DFS with the visit point moved before, between, or after the recursive calls.

  • Recursion — Tree traversal is the canonical recursive algorithm: process the current node, recurse on each child. The call stack manages the traversal state so you don't have to.

  • DOM Walking — The DOM is a tree. Walking it with childNodes is the same recursive DFS you write for a BST. querySelectorAll is DFS with a predicate. TreeWalker is the same algorithm exposed as a standard library.

  • React Fiber — React Fiber walks the component tree using the same depth-first order as tree traversal — but reifies the call stack as a singly-linked list of Fiber nodes so the traversal can be paused between nodes.