Binary tree depth-first search Explained Step by Step in JavaScript

The idea

A binary tree is a set of nodes where each node holds a value and points to at most two children: a left child and a right child. The top node is the root. A node with no children is a leaf. The empty spot where a child is missing is written as null.

Depth-first search, or DFS, visits the tree by walking down. From a node it first explores the whole left subtree (the node's left child and everything below it), then the whole right subtree, and only then is that node finished. A function that calls itself does this naturally: to visit a node, visit its left child, then visit its right child.

The only choice is when you do the work for the node itself. Doing it before the children is called preorder, between them is inorder, and after them is postorder. The walk is the same in all three; only the moment you record the node changes.

An everyday example

Exploring a cave with a ball of string

You explore a cave where every tunnel splits into at most two smaller tunnels. At each split you always take the left tunnel first and unroll string behind you. When you reach a dead end, you follow the string back to the last split and take the right tunnel. When both tunnels of a split are explored, you walk back one more split. You never miss a tunnel, and you never explore one twice.

How the example maps to the code
In the example	In the code
A split in the cave	A node with `node.left` and `node.right`
Taking the left tunnel first	`visit(node.left)` before `visit(node.right)`
A dead end	`node === null`, so `return`
Following the string back	A recursive call returning to its caller
Writing the split's name in your notebook	`preorder.push(node.val)` (or in the inorder or postorder spot)

From the slow way to binary tree depth-first search

Say you must add up every value in a tree, or list them all. The first idea is to write code for each level: look at the root, then at root.left and root.right, then at their children, and so on. That works only for a tree whose depth you know in advance, and real trees can be any depth.
Notice that every child is itself the root of a smaller tree, called a subtree. The left child and everything under it is a complete binary tree of its own. So the job "handle this tree" splits into three smaller jobs: handle the node, handle the left subtree, and handle the right subtree. Two of those jobs are the same job on a smaller tree.
A function that calls itself does exactly this. visit(node) handles one node, then calls visit(node.left) and visit(node.right). Each call gets a strictly smaller tree, and the smallest tree of all is the empty one, null, where there is nothing to do. That empty case is where every chain of calls stops.
The last choice is when to record the node: before the two calls (preorder), between them (inorder), or after them (postorder). The walk itself is the same every time. It goes all the way down the left side first, comes back up, and then tries the right side. That loop of going deep, returning, and trying the next branch is depth-first search.

How it works

Write a function visit(node) that handles one node and everything below it.
If node is null, there is nothing here: return right away. This stops the recursion.
For preorder, record node.val now, before the children.
Call visit(node.left) to finish the whole left subtree.
For inorder, record node.val now, between the two children.
Call visit(node.right) to finish the whole right subtree.
For postorder, record node.val now, after both children. Then start everything with visit(root).

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 dfs(root) {
const preorder = [];
const inorder = [];
const postorder = [];
function visit(node) {
if (node === null) return;
preorder.push(node.val);
visit(node.left);
inorder.push(node.val);
visit(node.right);
postorder.push(node.val);
}
visit(root);
return { preorder, inorder, postorder };
}

How fast it is

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

Every node is visited once. The call stack holds one call per node on the current path, so memory grows with the height h, which is between log n for a balanced tree and n for a straight chain.

Best caseO(n)
Any tree, even a single node or a perfectly balanced tree. A full walk can't skip anything, so each of the n nodes is visited once.
Average caseO(n)
A random tree: one visit per node and one quick null check per empty child slot.
Worst caseO(n)
A straight chain of 10,000 nodes. The time is still O(n), but this is the shape that makes the call stack as deep as the tree.

Common mistakes

Forgetting the null check. The code then reads .left of null and throws a TypeError. Always handle the empty child first.
Checking only node.left === null && node.right === null to stop. That handles leaves, but a node with one child still calls visit(null) on the other side. Stop on null itself, not on leaves.
Returning a value from the recursive calls but ignoring it, as in visit(node.left); when you meant const left = visit(node.left);. Store and combine what the children return.
Using recursion on a tree that can be tens of thousands of levels deep, such as a long linked chain. Switch to an explicit stack to avoid a stack overflow.

When to use it

Look for these clues in a problem:

The input is a tree, and the answer for a node depends on its children, like a depth, a size, or a total.
You must look at every node once, and the order inside each branch matters.
The question talks about subtrees, mirror images, or comparing two trees node by node.
The data is nested: folders inside folders, components inside components, panes split into panes.

Check yourself

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

Why does the code test node === null instead of testing for a leaf?

A node with one child still calls visit on its missing side. Stopping at null covers leaves, one-child nodes, and the empty tree with a single line.

How many times is visit called on a tree with n nodes?

2n + 1 times: once per node and once per empty child slot. A tree with n nodes always has n + 1 empty slots, as the trace shows with 5 nodes and 6 null calls.

Which order would you use to free or delete every node, and why?

Postorder. A node is handled only after both of its children are done, so you never lose the pointer to a child before visiting it.

Can you rebuild the trace's tree from its preorder [7, 3, 5, 9, 8] alone?

No. Many shapes give the same preorder. You also need the inorder, or null markers, to know where each subtree ends.

How many calls wait on the stack at most for a perfect tree of 1,023 nodes?

11. The tree has 10 levels, so the deepest real node is the 10th call down, and its call on a null child is the 11th.

Practice problems

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

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 rule each call keeps: when visit(node) returns, every node in node's subtree has been added to each of the three lists exactly once, and nothing outside that subtree was touched. For null this is true at once, because an empty subtree has no nodes and the call returns without doing anything.

Now assume the rule holds for the two smaller subtrees. Then visit(node) adds node once to each list, the left call adds every left node once, and the right call adds every right node once. The two subtrees share no nodes, so nothing is added twice. Applying the same reasoning to bigger and bigger subtrees, the rule holds for the root, so every node is in every list once.

The walk ends because each call goes to a child, one level deeper, and a tree has a finite depth. Every chain of calls reaches null after at most h + 1 calls. The three orders come only from where each push sits: preorder pushes before both recursive calls, so a parent comes before everything below it, and postorder pushes after both, so a parent comes after everything below it.

Going deeper

4 more ideas

Why every node is visited exactly once

Each node has exactly one parent, except the root. visit(root) reaches the root, and each call reaches a node's two children. So every node is reached through its one parent, once. The null check stops the walk at the bottom of every branch, so it always ends.

Which order to pick

Use preorder when a parent must be handled before its children, like copying a tree or printing an outline. Use inorder on a binary search tree, because it lists the values in sorted order. Use postorder when a node needs answers from its children first, like a height or a total size: the children finish, then the parent combines their results.

Time and memory

Each node is visited once and does a fixed amount of work, so the time is O(n) for n nodes. The memory is the call stack: one waiting call for each node on the current path from the root. That is O(h), where h is the tree's height. A balanced tree has h about log n, but a tree shaped like a straight line has h = n.

When the tree is very deep

Each recursive call uses a little stack memory, and JavaScript engines stop at a depth of roughly ten thousand calls with RangeError: Maximum call stack size exceeded. For trees that may be that deep, such as a long chain built from user data, use an explicit stack instead (see iterative tree traversal).

Work it by hand

Every step in a table, with why

Walk a 5-node tree once and fill all three lists. Node 3 has only a right child and node 9 has only a left child, so the trace shows both kinds of missing child.

root = [7, 3, 9, null, 5, 8] (`3` has right child `5`, `9` has left child `8`)

Step	`node.val`	What happens	`preorder`	`inorder`	`postorder`	Why
1	7	enter	[7]	[]	[]	The walk starts at the root. Preorder records `7` before looking at either child.
2	3	enter	[7, 3]	[]	[]	`visit(7.left)` moves to `3`, and preorder records it at once.
3	3	left side done	[7, 3]	[3]	[]	`3.left` is `null`, so that call returns right away. The left side of `3` is finished, so inorder records `3`.
4	5	enter	[7, 3, 5]	[3]	[]	`visit(3.right)` reaches `5`.
5	5	left side done	[7, 3, 5]	[3, 5]	[]	`5.left` is `null`, so inorder records `5` right away.
6	5	both sides done	[7, 3, 5]	[3, 5]	[5]	`5.right` is also `null`. Both children are done, so postorder records `5` and the call returns to `3`.
7	3	both sides done	[7, 3, 5]	[3, 5]	[5, 3]	Back at `3`, its right subtree is finished, so postorder records `3`. The call returns to `7`.
8	7	left side done	[7, 3, 5]	[3, 5, 7]	[5, 3]	The whole left subtree of `7` is done. Only now does inorder record `7`, after `3` and `5`.
9	9	enter	[7, 3, 5, 9]	[3, 5, 7]	[5, 3]	`visit(7.right)` starts the right subtree at `9`.
10	8	enter	[7, 3, 5, 9, 8]	[3, 5, 7]	[5, 3]	`9` has a left child, `8`, so the walk goes down to it first.
11	8	left side done	[7, 3, 5, 9, 8]	[3, 5, 7, 8]	[5, 3]	`8.left` is `null`, so inorder records `8`.
12	8	both sides done	[7, 3, 5, 9, 8]	[3, 5, 7, 8]	[5, 3, 8]	`8.right` is `null` too, so postorder records `8` and the call returns to `9`.
13	9	left side done	[7, 3, 5, 9, 8]	[3, 5, 7, 8, 9]	[5, 3, 8]	The left side of `9` is done, so inorder records `9`.
14	9	both sides done	[7, 3, 5, 9, 8]	[3, 5, 7, 8, 9]	[5, 3, 8, 9]	`9.right` is `null`, so `9` is finished and postorder records it.
15	7	both sides done	[7, 3, 5, 9, 8]	[3, 5, 7, 8, 9]	[5, 3, 8, 9, 7]	Both subtrees of the root are done. Postorder records `7` last, and the first call returns.

preorder = [7, 3, 5, 9, 8], inorder = [3, 5, 7, 8, 9], postorder = [5, 3, 8, 9, 7]. The trace ends when the call on 7 returns. There were 11 calls in all: 5 on real nodes and 6 on null children.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Binary tree depth-first search	`O(n)`	`O(h)`	The default for whole-tree questions where a node's answer comes from its children or from its ancestors.
Level-order traversal	`O(n)`	`O(w)`	You need levels, rows, or the shallowest match. Memory grows with the widest level `w` instead of the height.
Iterative traversal with a stack	`O(n)`	`O(h)`	The tree may be thousands of levels deep, or you need to pause the walk and continue later.
Morris traversal	`O(n)`	`O(1)`	You need inorder with constant extra memory and may change pointers for a short time.

Extra memory: O(h) for the call stack, where h is the height: about log₂ n waiting calls for a balanced tree (20 for a million nodes) and n for a chain. The three output lists add O(n).

How the steps grow

Binary tree depth-first search, Level-order traversal, Iterative traversal with a stack, Morris traversal O(n)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Binary tree depth-first search	10	1,000	1 million
Level-order traversal	10	1,000	1 million
Iterative traversal with a stack	10	1,000	1 million
Morris traversal	10	1,000	1 million

Inputs that need care

5 tricky inputs

An empty tree: root = null: visit(null) returns on line 6 before touching anything, so all three lists come back empty. No special check is needed before the first call.
One node: root = [42]: Both child calls hit null and return, so 42 lands in all three lists: [42], [42], and [42].
A node with only one child, like 3 in the trace: The missing side still gets a call, visit(null), which returns at once. That's why the code checks node === null and not "is this a leaf".
A chain 50,000 nodes deep: The recursion needs 50,000 waiting calls and throws RangeError: Maximum call stack size exceeded in most engines. Use an explicit stack (iterative tree traversal) for input you don't control.
Duplicate values, such as two nodes that both hold 4: The walk follows pointers, not values, so both nodes are visited and both 4s appear in each list. To tell them apart, compare node objects, not node.val.

Variations and follow-ups

Twists interviewers add

Return a value instead of filling a list

Many questions want one number per subtree: its height, its size, or its sum. Make visit return that number and combine the children's answers, for example return 1 + Math.max(visit(node.left), visit(node.right)) for the height. This is postorder in another form, and it's the base of tree DP.

Pass information down

Some questions need something from the ancestors, like the depth or the range of values a search tree allows at this spot. Add a parameter: visit(node, depth) calls visit(node.left, depth + 1). Each call gets its own copy of the parameter, so nothing has to be undone afterwards.

Walk two trees together

To check whether two trees are equal, or mirror images of each other, call visit(a, b) on matching nodes. Return false as soon as one is null and the other isn't, or the values differ. For a mirror check, pair a.left with b.right.

Trees with many children

Nodes like DOM elements have a list of children instead of left and right. Replace the two calls with a loop: for (const child of node.children) visit(child). Preorder and postorder still make sense, but inorder doesn't, because there is no single middle spot.

In an interview

Spot it, explain it, answer follow-ups

Spot it when the problem gives you a root and asks about the whole tree: a height, a count, a sum, "is it symmetric", "are these two trees equal". If each node's answer depends on its children's answers, it's DFS with the work in postorder.
Say out loud, as one sentence, what a call returns: "visit(node) returns the height of the subtree rooted at node". The base case (null returns 0) and the combine step then follow from that sentence.
Test by hand on an empty tree, a single node, and a chain leaning one way. The chain catches code that assumes both children exist.
Expect "what if the tree is very deep?". Answer: the call stack may overflow at around ten thousand levels, so switch to an explicit stack. The time stays O(n) and the memory stays O(h), but now it lives in normal memory, which is much larger.

Where frontend code uses it

The same idea in real UI code

document.querySelectorAll returns elements in document order, which is the preorder of the DOM tree: a parent comes before its children, and earlier siblings before later ones.
React's work loop walks the fiber tree depth-first: it goes down into child first, and when a branch is finished it moves to the sibling, then back up through return.
Babel and ESLint walk a program's syntax tree depth-first. Their visitors can run code when entering a node (preorder) and when exiting it (postorder).
A file explorer that computes folder sizes adds up the children before the parent, which is a postorder walk.

Binary tree depth-first search

The idea

An everyday example

Exploring a cave with a ball of string

From the slow way to binary tree depth-first search

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 every node is visited exactly once

Which order to pick

Time and memory

When the tree is very deep

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Return a value instead of filling a list

Pass information down

Walk two trees together

Trees with many children

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Exploring a cave with a ball of string

From the slow way to binary tree depth-first search

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 every node is visited exactly once

Which order to pick

Time and memory

When the tree is very deep

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Return a value instead of filling a list

Pass information down

Walk two trees together

Trees with many children

In an interview

Where frontend code uses it

Related algorithms