ALGORITHMS IN FRONTEND WORK · FOUNDATION

Walking the DOM tree

Visit every element of a page in document order by going deep first, using a stack of elements still to visit.

Time O(n)Space O(n)9 practice problemsStep-through picture

The idea

A web page is a tree. The html element holds head and body, body holds sections, sections hold paragraphs, and so on. Each element has a list of children. This tree is the DOM, the Document Object Model.

Many tasks need to visit every element: find all img elements, collect every id, or check that each label points at a real input. The usual order is document order, the order the tags appear in the HTML source. That is a depth-first, parent-before-children walk, called preorder.

You can write the walk with recursion, but very deep pages can overflow the call stack. A loop with your own stack array does the same walk safely: pop an element, visit it, and push its children in reverse so the first child comes out next.

An everyday example

Reading a book's table of contents

A table of contents lists chapter 1, then its sections 1.1 and 1.2, and the subsections inside 1.1 before 1.2. Then chapter 2. You read a heading and, before moving on, read everything nested under it. To remember where to come back to, you keep a pile of sticky notes: when you open a chapter, you put notes for its sections on the pile, last section at the bottom, so the first section is on top and gets read next.

How the example maps to the code
In the example	In the code
A heading in the table of contents	An element `node` with `node.children`
The pile of sticky notes	The array `stack`
Taking the top note and reading it	`const node = stack.pop()` then `ids.push(node.id)`
Adding notes for the sections, last one first	Pushing `children` from the end to the start

From the slow way to walking the dom tree

Start with the obvious way: a recursive function. visit(node) records node.id, then calls visit on each child in order. It is short and gives document order. But every level of nesting adds one frame to the JavaScript call stack, and that stack has a fixed size. A tree a few thousand levels deep, from generated markup or hostile input, makes it throw RangeError: Maximum call stack size exceeded.
So ask what the recursion is really remembering. At any moment, the open calls hold the children that are still waiting to be visited, for every ancestor of the current element. That is just a list of elements to visit later. We can keep that list ourselves, in a normal array, which can grow to millions of items without any limit on depth.
Which kind of list? Everything inside the first child must be visited before the second child. So the elements found most recently must come out first. Last in, first out is a stack: push to add an element, pop to take the newest one.
One detail is left. If we push the children in their normal order, the last child ends up on top and comes out first, which gives a mirror image of the page. Pushing them from last to first puts children[0] on top. Now repeat: pop an element, visit it, push its children in reverse, until the stack is empty. That loop is the iterative walk of the DOM tree in document order.

How it works

Start a stack holding just the root, and an empty list ids for the visit order.
While the stack isn't empty, pop the top element: node = stack.pop().
Visit it. Here, visiting means ids.push(node.id); in other tasks it could be testing a tag or counting.
Push its children onto the stack from last to first, so the first child is on top.
When the stack is empty, every element has been visited once, in document order.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function collectIds(root) {
const ids = [];
const stack = root ? [root] : [];
while (stack.length > 0) {
const node = stack.pop();
ids.push(node.id);
const children = node.children ?? [];
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i]);
}
}
return ids;
}

How fast it is

Time	`O(n)`
Extra memory	`O(n)`

Each of the n elements is pushed and popped once. The stack never holds more than n elements, and for a balanced page it holds far fewer.

Best caseO(n)
Any tree. The loop has no early exit: it visits all n elements even if the first one was the one you wanted.
Average caseO(n)
A typical page: each element costs one push, one pop, and one visit.
Worst caseO(n)
Still n pops. The shape only changes memory: a ul with 5,000 li children puts all 5,000 on the stack at once.

Common mistakes

Pushing children in their normal order onto a stack. The last child comes out first and the order is no longer the document order.
Using queue.shift() in a loop over a huge tree. shift moves every remaining item, so it can turn O(n) into O(n^2). Keep a head index instead.
Recursing on trees that can be thousands of levels deep, such as generated or malicious HTML. The call stack can overflow; an explicit stack can't.
Changing the tree while walking it, such as removing the current element. Collect what to change first, then change it after the walk.

When to use it

Look for these clues in a problem:

The input is a nested tree of elements, components, menu items, comments, or folders.
You must visit every node, or find nodes that match a rule, in the order they appear on the page.
The answer depends on a node's ancestors, such as its depth or the path from the root.
The tree can be very deep, so an explicit stack is safer than recursion.

Check yourself

Answer each one in your head first, then open it.

Why are the children pushed from last to first?

A stack gives back the newest item first. Pushing the last child first leaves children[0] on top, so the first child is visited next and the order matches the HTML.

A ul has 50 li children and nothing else. What is the most the stack ever holds?

50. After popping the ul, all 50 li elements are pushed at once, and then each pop removes one.

Why can't this loop overflow the call stack when recursion can?

It never calls itself. The waiting elements live in an ordinary array, which can grow as large as memory allows, while the call stack has a small fixed limit.

What goes wrong if the same object appears as a child of two parents?

It is pushed once per parent, so it and everything inside it are visited twice. A real DOM can't do this, but plain JSON data can; add a seen set to skip repeats.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 9 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

#705Match a Descendant Selector

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule, true at the top of every loop. ids holds the first part of the document order, with nothing skipped. And the stack, read from the top down, holds the roots of every subtree that hasn't been visited yet, in document order. A subtree here means an element plus everything nested inside it. At the start, ids is empty and the stack holds only root, so the rule is true.

Each loop keeps the rule. The top of the stack is the first element, in document order, that hasn't been visited, so visiting it next is correct. In document order, an element is followed by its first child's subtree, then its second child's subtree, and so on, and only then by whatever came after the element. Replacing the element on the stack with its children, first child on top, says exactly that.

The loop ends because each element is pushed once, when its parent is popped, and every element in a tree has exactly one parent. So there are exactly n pops. When the stack is empty, there is no unvisited subtree left, and by the rule ids holds the whole document order. If the input were a graph where one node had two parents, it would be pushed twice; that needs a seen set, as in graph search.

Going deeper

3 more ideas

Why reverse order gives document order

A stack gives back the last thing you put in. If the children of main are p then ul, pushing ul first and p second means p is popped next. Everything inside p is pushed on top of ul, so all of p's descendants are visited before ul. That is exactly the order the tags appear in the HTML.

How fast it is

Each element is pushed once and popped once, so the walk is O(n) for n elements. The stack holds, at most, the siblings still waiting along the current path, which is O(n) in the worst case and usually much smaller.

Breadth-first instead

Using a queue instead of a stack (take from the front with shift, or keep a head index) visits the tree level by level: the root, then all its children, then all grandchildren. That fits questions like "which elements are nested exactly 3 levels deep?"

Work it by hand

Every step in a table, with why

Collect the ids of a small blog post in document order. The aside waits on the stack while the whole section is walked.

root = article#post { h2#head, section#body { p#p1, figure#fig { img#pic } }, aside#notes }

Step	Popped `node`	Pushed (last child first)	`stack` after (top at right)	`ids`	Why
1	(start)	post	[post]	[]	The `root` is not `null`, so the stack starts with just `post`.
2	post	notes, body, head	[notes, body, head]	post	Visit `post`. Its 3 children are pushed from last to first, so `head`, the first child, is on top.
3	head	none	[notes, body]	post, head	`head` has no `children` field, so `?? []` gives an empty list and nothing is pushed.
4	body	fig, p1	[notes, fig, p1]	post, head, body	Visit `body`. Its children go on top of `notes`, so all of `body`'s inside is visited before `notes`.
5	p1	none	[notes, fig]	post, head, body, p1	`p1` is a leaf. The stack shrinks by one.
6	fig	pic	[notes, pic]	... body, p1, fig	Visit `fig` and push its only child, `pic`.
7	pic	none	[notes]	... p1, fig, pic	`pic` is the deepest element. After it, only `notes` is left.
8	notes	none	[]	... fig, pic, notes	`notes` has waited since step 1. Now the stack is empty, so the loop stops.

It returns [post, head, body, p1, fig, pic, notes], the order the tags appear in the HTML. There were 7 pops for 7 elements, and the stack never held more than 3 items.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Walking the DOM tree	`O(n)`	`O(n)`	You need every element in document order and the tree may be very deep, or you're writing it in an interview.
Recursive preorder	`O(n)`	`O(n)`	The tree is known to be shallow, like a menu or a component tree, and short code matters more than handling extreme depth.
Breadth-first with a queue	`O(n)`	`O(n)`	You need elements level by level, or the match closest to the root.
`TreeWalker` with parent and sibling links	`O(n)`	`O(1)`	You're in a real browser. It is built in, needs no extra memory because each node knows its parent and next sibling, and can skip subtrees with a filter.

Extra memory: O(n) in the worst case: a root with n - 1 direct children fills the stack with n - 1 items after the first pop. A single long chain is the opposite: the stack never holds more than 1 item, which is exactly the shape where recursion uses the most memory. The ids result is O(n) too.

How the steps grow

Walking the DOM tree, Recursive preorder, Breadth-first with a queue, TreeWalker with parent and sibling links O(n)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Walking the DOM tree	10	1,000	1 million
Recursive preorder	10	1,000	1 million
Breadth-first with a queue	10	1,000	1 million
`TreeWalker` with parent and sibling links	10	1,000	1 million

Inputs that need care

6 tricky inputs

root is null or undefined: stack starts as [], the while loop never runs, and the function returns [].
A leaf with no children field at all, like { id: "pic" }: node.children ?? [] gives an empty list, so the inner loop pushes nothing.
A real DOM element: element.children is an HTMLCollection of elements only, with no text or comment nodes. It has length and indexes, so the same loop works. Use childNodes instead if you need text nodes. Elements without an id give "".
A web component with a shadow root, or a template element: children does not include what is inside element.shadowRoot or template.content. To walk into them, also push the children of the open shadow root or of the template's content.
A chain 100,000 elements deep: The stack holds at most 1 item at a time, so the walk finishes. A recursive version would overflow the call stack long before that depth.
A script removes an element that is already on the stack: The stack still holds a reference, so the removed element is visited anyway. Collect what you want to change during the walk, and change it after.

Variations and follow-ups

Twists interviewers add

Breadth-first, level by level

Swap the stack for a queue: take from the front with a head index and push children in normal order. The walk then visits the root, all of its children, then all grandchildren. Use it to find the shallowest match, or to group elements by depth.

Stop at the first match

Return as soon as an element passes the test, like document.querySelector does: it gives the first match in document order. The best case drops to O(1) when the root matches.

Carry depth or a path

Push pairs like [node, depth] and push children with depth + 1. Now each visit knows how deep it is, which is what you need to indent an outline of headings or to build a breadcrumb.

Skip whole subtrees with `TreeWalker`

document.createTreeWalker(root, NodeFilter.SHOW_ELEMENT, filter) walks in the same order. If filter returns NodeFilter.FILTER_REJECT, a TreeWalker skips that element and everything inside it, while FILTER_SKIP skips only the element. It moves with parent and sibling links, so it needs no stack at all.

In an interview

Spot it, explain it, answer follow-ups

Spot it from words like "nested", "children", "every element that matches", "in the order they appear", or a tree of comments, folders, or menu items.
Say the rule out loud: "the stack holds subtrees that are still waiting; I pop one, visit it, and push its children in reverse so the first child comes out next". Then point out why you chose a stack over recursion: depth.
Test by hand on 4 shapes: an empty tree, a single element, a long chain, and one element with many children. Check the output against the order of the tags in the HTML source.
Expect the follow-up "can you do it with no extra memory?". Yes, if each node has parent and nextSibling links: go to the first child if there is one; otherwise go to the next sibling; otherwise climb parents until one has a next sibling. That is how TreeWalker.nextNode() and React's fiber walk move.

Where frontend code uses it

The same idea in real UI code

document.querySelectorAll and getElementsByTagName return elements in document order, which is this preorder walk.
The DOM's TreeWalker and NodeIterator (made with document.createTreeWalker) walk the tree in the same order, with a filter for which nodes to visit.
React walks its fiber tree depth first, following child, sibling, and return pointers, when it renders and commits updates.
Accessibility checkers and test tools like Testing Library walk the DOM to find elements by role, label, or text.

Walking the DOM tree

The idea

An everyday example

Reading a book's table of contents

From the slow way to walking the dom tree

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why reverse order gives document order

How fast it is

Breadth-first instead

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Breadth-first, level by level

Stop at the first match

Carry depth or a path

Skip whole subtrees with `TreeWalker`

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Reading a book's table of contents

From the slow way to walking the dom tree

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why reverse order gives document order

How fast it is

Breadth-first instead

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Breadth-first, level by level

Stop at the first match

Carry depth or a path

Skip whole subtrees with TreeWalker

In an interview

Where frontend code uses it

Related algorithms

Skip whole subtrees with `TreeWalker`