Algorithms from zero
Tree traversals
You know how to walk left and right through a tree by following pointers. But in what order do you visit the nodes? Do you look at the node first, or explore its children first? Different orders answer different questions. Visit the node before its children, and you can build a copy top-down. Visit the node after its left child in a binary search tree, and you get sorted order. Visit it after both children, and you can compute subtree results from the ground up. This lesson teaches the three canonical orders and why you would pick each one.
After this lesson you can write the three depth-first tree traversals (pre-order, in-order, post-order) as recursive functions, trace each on a concrete tree to predict the visiting order, explain when and why each is used, and recognize when a problem requires a specific traversal order.
What is a traversal?
A traversal is a systematic visit to every node in a tree. The order in which you visit matters because it determines what information is available when you process each node.
There are many traversal orders, but the three most common are depth-first traversals that visit the root before exploring all its descendants. They differ in when the root is visited relative to its children:
- Pre-order: Visit root, then left subtree, then right subtree. (Node, Left, Right)
- In-order: Visit left subtree, then root, then right subtree. (Left, Node, Right)
- Post-order: Visit left subtree, then right subtree, then root. (Left, Right, Node)
All three are recursive: to traverse a tree, process the root according to the order, then recursively traverse the left and right subtrees.
Why three different orders?
Each order is a tool for different jobs. Pre-order processes a parent before its children (useful for copying a tree, or marking the distance from the root). In-order on a binary search tree gives sorted order—the node’s value comes out between all smaller values (in the left subtree) and all larger values (in the right subtree). Post-order processes a parent after both children (useful for deleting a tree or computing subtree heights). The choice depends on whether you need ancestors’ context, sorted output, or results from descendants.
Pre-order traversal: process the root first
In pre-order, visit the current node, then recursively traverse its left subtree, then its right subtree.
1
function preOrder(node) {
2
if (node === null) return;
3
4
// Visit (process) the node
5
console.log(node.value);
6
7
// Traverse left subtree
8
preOrder(node.left);
9
10
// Traverse right subtree
11
preOrder(node.right);
12
}
- L1 Recursive function: takes a node (or null for an empty subtree).
- L2 Base case: if the node is null, there is nothing to visit.
- L5 Visit the current node (here, print its value).
- L8 Recursively traverse the left subtree.
- L11 Recursively traverse the right subtree.
Example: For the tree:
1
/ \
2 3
/
4Pre-order visits in this order: 1 → 2 → 4 → 3.
In-order traversal: visit the node between its children
1
function inOrder(node) {
2
if (node === null) return;
3
4
// Traverse left subtree
5
inOrder(node.left);
6
7
// Visit (process) the node
8
console.log(node.value);
9
10
// Traverse right subtree
11
inOrder(node.right);
12
}
- L1 Recursive function: takes a node (or null for an empty subtree).
- L2 Base case: if the node is null, there is nothing to visit.
- L5 Recursively traverse the left subtree first.
- L8 Visit the current node after its left subtree.
- L11 Recursively traverse the right subtree.
Example: For the same tree:
1
/ \
2 3
/
4In-order visits in this order: 4 → 2 → 1 → 3.
Post-order traversal: visit the node after both children
1
function postOrder(node) {
2
if (node === null) return;
3
4
// Traverse left subtree
5
postOrder(node.left);
6
7
// Traverse right subtree
8
postOrder(node.right);
9
10
// Visit (process) the node
11
console.log(node.value);
12
}
- L1 Recursive function: takes a node (or null for an empty subtree).
- L2 Base case: if the node is null, there is nothing to visit.
- L5 Recursively traverse the left subtree.
- L8 Recursively traverse the right subtree.
- L11 Visit the current node after both subtrees.
Example: For the same tree:
1
/ \
2 3
/
4Post-order visits in this order: 4 → 2 → 3 → 1.
Running all three on a concrete tree
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
preOrder(root);
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
inOrder(root);
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
postOrder(root);
Time complexity
Each of the three traversals visits every node in the tree exactly once. If the tree has n nodes, we make n visits plus the recursive calls to reach those nodes. Every node is processed once, so the time is O(n) for all three traversals.
Space complexity
The space used is the depth of the call stack. When the recursion goes down the tree, each recursive call stays on the call stack until it returns. The maximum depth of the call stack equals the height of the tree, h.
- Best case (balanced tree): O(log n) space for a height of log n.
- Worst case (chain): O(n) space for a height of n (if every node has only one child).
In typical balanced trees, O(log n) space. In skewed trees, O(n) space.
For the tree: 2 / \ 1 3 Which is the pre-order traversal?
For the same tree, which is the in-order traversal?
For the same tree, which is the post-order traversal?
When you traverse a binary search tree with in-order, what property does the output have?
Pre-order traversal is most useful for which task?
lesson.inset.undefined
Do not confuse the order names. Pre- means “before” (visit the node before children). Post- means “after” (visit after children). In- means “in between” (visit between left and right children). A mnemonic: Pre (PREsent the root), In (In between), Post (POST-dated, arrives last).
lesson.inset.undefined
Trace it yourself. Draw a binary tree with 5 nodes. For each traversal (pre, in, post), trace the visiting order by hand. Write down the sequence. This is the fastest way to lock in the order differences.
lesson.inset.undefined
Empty trees and single nodes. If a tree is empty (null), the traversal does nothing. If a tree is a single node with no children, all three traversals visit just that one node. Edge cases make good test inputs.
Why do we need three different traversal orders instead of just one?
A traversal is a systematic visit to every node in a tree. Three depth-first traversals differ in when they visit a node relative to its children. Pre-order visits the node first, then left, then right (useful for copying, top-down processing). In-order visits left, node, right (gives sorted order on a BST). Post-order visits left, right, node (useful for deletion, computing subtree results bottom-up). All three are recursive: process the root according to the order, then recursively traverse subtrees. All three run in O(n) time (visit each node once) and O(h) space (recursion depth equals tree height). Next lesson covers level-order traversal (BFS), which uses a queue instead of recursion.