Tree Traversals

what is it

Start here

A tree branches, so 'visit every node' has more than one meaning. Where do you go first — down, or across? The three classic traversals all visit every node exactly once, and differ by a single decision: when does a node visit itself, relative to its children?

In-order visits the left child, then itself, then the right child. On a search tree this is quietly magical: it spits every value out in sorted order, for free.

Pre-order visits itself first, then its children. You meet every parent before its kids — which is exactly what you need to copy a tree or print a nested outline.

Post-order visits both children before itself. You finish with every child before its parent — which is how you safely delete a tree, freeing the leaves before the branch that holds them.

Watch the output strip fill up under the tree. The tree never changes; only the order you touch the nodes does — and that order is chosen to match the job.

real-life analogy

Picture it

Reading a book's table of contents

Pre-order is reading top to bottom: Chapter 1, then its sections, then Chapter 2. You see each heading before its sub-headings. Post-order is the opposite — you'd tally every sub-section before declaring the chapter done, the way you'd total the parts before the whole.

interactive visualization

Watch it run

your numbers

The tree is built first, then walked three different ways.

20

30

40

50

60

70

80

There's more than one order to visit every node in a tree. The three classics differ by just one thing: when a node visits itself, relative to its two children.

step 01/28

target · placed
on the path

space · play ← → · step

1	`function inorder(node, out) { // left · self · right`
2	`if (node === null) return;`
3	`inorder(node.left, out);`
4	`out.push(node.value);`
5	`inorder(node.right, out);`
6	`}`
7
8	`function preorder(node, out) { // self · left · right`
9	`if (node === null) return;`
10	`out.push(node.value);`
11	`preorder(node.left, out);`
12	`preorder(node.right, out);`
13	`}`
14
15	`function postorder(node, out) { // left · right · self`
16	`if (node === null) return;`
17	`postorder(node.left, out);`
18	`postorder(node.right, out);`
19	`out.push(node.value);`
20	`}`

variables right now

Nothing in play yet — press play.

comparisons 0moves 0

the dry run · every step, in words

28 steps

complexity

What it costs

best case: O(n)
average: O(n)
worst case: O(n)
extra memory: O(n)

Every traversal touches all n nodes once, so they're all O(n) time. The space is the recursion depth — O(height), which is O(n) in the worst case of a lopsided tree and O(log n) when balanced.

O(1)
O(log n)
O(n) · this one
O(n log n)
O(n²)

common mistakes

Common traps

Expecting pre-order or post-order to come out sorted.
Only in-order yields sorted output, and only on a search tree. Pre- and post-order have their own uses, but sorted order isn't one of them.
Forgetting the null check at the top of the recursion.
Every traversal must return immediately on a null node. Without it, you follow an empty branch and crash.
Mixing up the visit position.
The only difference between the three is where 'visit myself' sits relative to the two recursive calls. Move that one line and you've changed the traversal entirely.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+80 XP

01Which traversal of a binary search tree produces sorted output?

02You want to delete a whole tree, freeing every node safely. Which order?

03What single thing distinguishes the three traversals?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.