Home/Trees/Traversals
Search algorithmsCTRL K

Traversals

· in-order, pre-order, post-order, level-order
/trees/traversals
VISITED
0/ 10
nodes in the output
TRAVERSAL
in-order
running now
DEPTH
0
of the current node
PHASE
1 / 4
of the four traversals
OUTPUT
so far
visitingentered, not yet visitedvisiteduntouched
10 keys · seed 7 · 68 steps
step 0 / 67
Keys10
traversals.ts
1
function inorder(node: Node | null, output: number[]) {
2
  if (node === null) return;
3
  inorder(node.left, output);
4
  output.push(node.key);
5
  inorder(node.right, output);
6
}
7
function preorder(node: Node | null, output: number[]) {
8
  if (node === null) return;
9
  output.push(node.key);
10
  preorder(node.left, output);
11
  preorder(node.right, output);
12
}
13
function postorder(node: Node | null, output: number[]) {
14
  if (node === null) return;
15
  postorder(node.left, output);
16
  postorder(node.right, output);
17
  output.push(node.key);
18
}
19
function levelorder(root: Node | null, output: number[]) {
20
  const queue = root ? [root] : [];
21
  while (queue.length > 0) {
22
    const node = queue.shift()!;
23
    output.push(node.key);
24
    if (node.left) queue.push(node.left);
25
    if (node.right) queue.push(node.right);
26
  }
27
}
CURRENT STEP
line 1

In-order: left subtree, node, right subtree. On a BST this yields the keys sorted.

// how it works

Understanding Traversals

traversals · four ways to read the same tree
01

The idea

A traversal visits every node once; the order in which a node is visited relative to its subtrees is what changes. In-order visits the left subtree, the node, then the right subtree, which on a binary search tree yields the keys sorted. Pre-order visits the node first, which is the order that lets you rebuild the tree. Post-order visits children before the parent, the order for freeing memory or evaluating an expression tree.

The three recursive traversals differ only in where the visit line sits. Level-order is different in kind: it uses a queue instead of the call stack, and reads the tree one depth at a time, which is breadth-first search applied to a tree.

02

The four stages

1
entera node, before its subtrees
2
visitappend the key to the output
3
returnback to the parent when done
4
queuelevel-order only: children wait in line
03

Complexity

best
O(n)every node exactly once
average
O(n)the shape of the tree does not matter
worst
O(n)same: linear in the number of nodes
space
O(h) · O(w)stack depth h, or the widest level w for level-order
04

Versus its siblings

PEAK EXTRA MEMORY · 1 000 000 NODES, BALANCED
in-order
20
pre-order
20
post-order
20
level-order
500,000
morris in-order
1
recursive traversals hold one frame per level; level-order holds half the tree in its queue
05

Pseudocode

INORDER(node): if node ≠ null: INORDER(left); visit(node); INORDER(right)
PREORDER(node): if node ≠ null: visit(node); PREORDER(left); PREORDER(right)
POSTORDER(node): if node ≠ null: POSTORDER(left); POSTORDER(right); visit(node)
LEVELORDER(root)
  queue ← [root]
  while queue not empty
    node ← dequeue; visit(node); enqueue its children
06

When to use

In-order for sorted output and range queries; pre-order to serialise or copy a tree; post-order to delete it or fold an expression.
Level-order for anything by depth: printing the tree, finding the shallowest match, computing width.
07

Pitfalls

Recursion depth equals the height: a degenerate tree with a million nodes overflows the stack. Use an explicit stack.
Level-order on a wide tree needs a queue as big as its widest level.
Pre-order alone does not identify a tree; with in-order it does, or with null markers.
08

History

The names pre-order, in-order and post-order were fixed by Knuth in the first volume of The Art of Computer Programming in 1968, where he also traced threaded trees back to Perlis and Thornton in 1960. Morris showed in 1979 that in-order can run in constant extra space by temporarily rewiring right pointers.

Back to Trees