Frontend

DOM Walking

Traversing the document tree — the same DFS you learned in DSA, wearing a browser hat.

Walking the DOM

function walkDOM(node) {
  visit(node);
  for (const child of node.childNodes) {
    walkDOM(child);
  }
}
 
walkDOM(document.body);

The DOM is a tree of nodes. Each Element has a childNodes list. Walking it recursively is depth-first pre-order traversal — exactly what you'd write for a binary tree, except each node can have N children instead of two.

The built-in you've never used

The browser ships TreeWalker — a DFS walker with filtering built in:

const walker = document.createTreeWalker(
  document.body,
  NodeFilter.SHOW_ELEMENT,
  (node) => node.tagName === 'P' ? NodeFilter.FILTER_ACCEPT : NodeFilter.FILTER_SKIP
);
 
while (walker.nextNode()) {
  console.log(walker.currentNode);
}

TreeWalker flattens the recursion into an iterator and lets you pass a filter function. Most engineers have never opened it. Most engineers have also written this function manually at least once.

querySelector under the hood

querySelectorAll does the same thing — DFS over the subtree, returning nodes that match a CSS selector. The selector is a predicate; the traversal is always DFS. When you write document.querySelectorAll('.item'), you're running a filtered tree walk.

Why this matters for React

React's component tree is a virtual DOM tree. Reconciliation (diffing the old tree against the new one) is also a tree traversal. React 15 did it recursively — same pattern as walkDOM. React 16 (Fiber) rewrote it to use an explicit linked list instead of recursion, allowing the traversal to pause between nodes and yield to the browser. Same algorithm, different execution model.

Connections

How this links to the rest

Tree Traversal — 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.
Recursion — Recursive DOM walking works because DOM nodes are a recursive data structure — an Element contains Elements. The recursion terminates at leaf nodes (no children).
Binary Tree — The DOM is a tree — not binary (elements have arbitrary children), but a tree in every other sense. Parent/child relationships, root, leaves, depth, subtrees — all the binary-tree vocabulary transfers. So do the algorithms: DFS, BFS, height calculation, subtree cloning.
Doubly Linked List — Every DOM node has previousSibling and nextSibling pointers — siblings under a parent form a doubly linked list. That's why DOM insertion and removal are O(1) when you hold a reference: the browser updates four pointers, it doesn't shift an array. Walking siblings is O(1) per step for the same reason.
Stack — Iterative DOM walking uses an explicit stack: push root, pop a node, visit, push its children. This is how many querySelectorAll implementations avoid recursion — DOMs can be deeper than the JS call stack allows.
Hash Table — getElementById is O(1), not a tree walk. Browsers maintain a hash map from id to element, bypassing traversal entirely. querySelector with a single-id selector short-circuits to the same lookup. The DOM is a tree, but the fast paths through it are hash tables.