Recursive Traversals

One Skeleton, Three Traversals

In the last chapter, you saw that every tree algorithm follows the same recursive shape: base case, recurse left, recurse right, combine. But we skipped something fundamental — when do you process the current node?

That single choice — process before, between, or after the recursive calls — gives you three completely different traversals. And they all come from the same DFS skeleton.

Here it is:

void dfs(Node* root) {
    if (!root) return;

    dfs(root->left);

    dfs(root->right);

}

There are exactly three places you can insert process(root):

Before both recursive calls → Preorder
Between the two recursive calls → Inorder
After both recursive calls → Postorder

That's it. Three traversals, one skeleton. The difference is a single line placement.

The Tree We'll Trace

Every example in this lesson uses this 7-node tree:

         1
       /   \
      2     3
     / \   / \
    4   5 6   7

Memorize it. You'll see it a dozen more times.

Preorder: Process, Then Explore

Preorder means: visit the current node first, then go left, then go right.

void preorder(Node* root, vector<int>& result) {
    if (!root) return;
    result.push_back(root->value);
    preorder(root->left, result);
    preorder(root->right, result);
}

You process the node the instant you arrive. You haven't seen any of its descendants yet. This is a "top-down" moment — you know everything about the path from the root to here, but nothing about what's below.

Preorder Trace

Step	Current Node	Action	Result So Far
1	1	Process 1, go left	[1]
2	2	Process 2, go left	[1, 2]
3	4	Process 4, go left	[1, 2, 4]
4	nullptr	Return	[1, 2, 4]
5	nullptr	Return	[1, 2, 4]
6	5	Process 5, go left	[1, 2, 4, 5]
7	nullptr	Return	[1, 2, 4, 5]
8	nullptr	Return	[1, 2, 4, 5]
9	3	Process 3, go left	[1, 2, 4, 5, 3]
10	6	Process 6, go left	[1, 2, 4, 5, 3, 6]
11	nullptr	Return	[1, 2, 4, 5, 3, 6]
12	nullptr	Return	[1, 2, 4, 5, 3, 6]
13	7	Process 7, go left	[1, 2, 4, 5, 3, 6, 7]
14	nullptr	Return	[1, 2, 4, 5, 3, 6, 7]
15	nullptr	Return	[1, 2, 4, 5, 3, 6, 7]

Preorder result: [1, 2, 4, 5, 3, 6, 7]

Notice the pattern: every node appears before all of its descendants. The root is always first.

Preorder visits nodes in the order you'd encounter them walking down the tree from root to leaves, left to right.

Inorder: Go Left First, Then Process, Then Go Right

Inorder means: fully explore the left subtree, then visit the current node, then explore the right subtree.

void inorder(Node* root, vector<int>& result) {
    if (!root) return;
    inorder(root->left, result);
    result.push_back(root->value);
    inorder(root->right, result);
}

You delay processing until after the entire left subtree is done. This is the traversal that produces sorted order on a BST.

Inorder Trace

Step	Current Node	Action	Result So Far
1	1	Go left (don't process yet)	[]
2	2	Go left	[]
3	4	Go left	[]
4	nullptr	Return	[]
5	4	Process 4, go right	[4]
6	nullptr	Return	[4]
7	2	Process 2, go right	[4, 2]
8	5	Go left	[4, 2]
9	nullptr	Return	[4, 2]
10	5	Process 5, go right	[4, 2, 5]
11	nullptr	Return	[4, 2, 5]
12	1	Process 1, go right	[4, 2, 5, 1]
13	3	Go left	[4, 2, 5, 1]
14	6	Go left	[4, 2, 5, 1]
15	nullptr	Return	[4, 2, 5, 1]
16	6	Process 6, go right	[4, 2, 5, 1, 6]
17	nullptr	Return	[4, 2, 5, 1, 6]
18	3	Process 3, go right	[4, 2, 5, 1, 6, 3]
19	7	Go left	[4, 2, 5, 1, 6, 3]
20	nullptr	Return	[4, 2, 5, 1, 6, 3]
21	7	Process 7, go right	[4, 2, 5, 1, 6, 3, 7]
22	nullptr	Return	[4, 2, 5, 1, 6, 3, 7]

Inorder result: [4, 2, 5, 1, 6, 3, 7]

For a BST, this would be sorted. For a general tree, it gives you nodes in "left-root-right" order at every level.

Inorder processes a node only after its entire left subtree is finished. For BSTs, this yields sorted order.

Postorder: Explore Everything, Then Process

Postorder means: fully explore the left subtree, fully explore the right subtree, THEN visit the current node.

void postorder(Node* root, vector<int>& result) {
    if (!root) return;
    postorder(root->left, result);
    postorder(root->right, result);
    result.push_back(root->value);
}

You process a node only after both children have reported back. This is the "bottom-up" moment — you already know everything about the subtree below.

Postorder Trace

Step	Current Node	Action	Result So Far
1	1	Go left	[]
2	2	Go left	[]
3	4	Go left	[]
4	nullptr	Return	[]
5	4	Go right	[]
6	nullptr	Return	[]
7	4	Process 4	[4]
8	2	Go right	[4]
9	5	Go left	[4]
10	nullptr	Return	[4]
11	5	Go right	[4]
12	nullptr	Return	[4]
13	5	Process 5	[4, 5]
14	2	Process 2	[4, 5, 2]
15	1	Go right	[4, 5, 2]
16	3	Go left	[4, 5, 2]
17	6	Go left → nullptr, go right → nullptr	[4, 5, 2]
18	6	Process 6	[4, 5, 2, 6]
19	3	Go right	[4, 5, 2, 6]
20	7	Go left → nullptr, go right → nullptr	[4, 5, 2, 6]
21	7	Process 7	[4, 5, 2, 6, 7]
22	3	Process 3	[4, 5, 2, 6, 7, 3]
23	1	Process 1	[4, 5, 2, 6, 7, 3, 1]

Postorder result: [4, 5, 2, 6, 7, 3, 1]

Every node appears after all its descendants. The root is always last.

Postorder processes a node only after both subtrees are fully resolved. This is the pattern behind max depth, diameter, and most "combine children's answers" problems.

Side-by-side comparison of preorder, inorder, and postorder visit orders on a 7-node tree

Summary Table

Traversal	Order	When to Use	Our Tree Result
Preorder	Root, Left, Right	Serialization, copying tree structure, top-down problems	[1, 2, 4, 5, 3, 6, 7]
Inorder	Left, Root, Right	BST sorted order, expression trees	[4, 2, 5, 1, 6, 3, 7]
Postorder	Left, Right, Root	Bottom-up computation, deletion, dependency resolution	[4, 5, 2, 6, 7, 3, 1]

Application: Max Depth as Postorder

You saw countNodes in Chapter 1. Here's max depth — same postorder shape:

int maxDepth(Node* root) {
    if (!root) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return 1 + max(leftDepth, rightDepth);
}

Why postorder? Because you need the depths of both subtrees before you can compute the depth at the current node. You can't know how deep the tree goes until you've gone all the way down.

Trace on our tree:

Node	leftDepth	rightDepth	Returns
4	0	0	1
5	0	0	1
2	1	1	2
6	0	0	1
7	0	0	1
3	1	1	2
1	2	2	3

Max depth = 3. Count the edges from root to any leaf: \(1 \to 2 \to 4\) is 2 edges, but this function counts nodes, so it returns 3. Consistent.

Application: Symmetric Tree as Simultaneous Recursion

Some problems need you to traverse two subtrees at the same time. Checking whether a tree is symmetric is the cleanest example.

A tree is symmetric if the left subtree is a mirror of the right subtree. "Mirror" means: the left child of the left subtree matches the right child of the right subtree, and vice versa.

bool isMirror(Node* leftSubtree, Node* rightSubtree) {
    if (!leftSubtree && !rightSubtree) return true;
    if (!leftSubtree || !rightSubtree) return false;
    if (leftSubtree->value != rightSubtree->value) return false;
    return isMirror(leftSubtree->left, rightSubtree->right) &&
           isMirror(leftSubtree->right, rightSubtree->left);
}

bool isSymmetric(Node* root) {
    if (!root) return true;
    return isMirror(root->left, root->right);
}

This is still the same DFS skeleton — but with two pointers instead of one, and the recursive calls cross over: left's left pairs with right's right, and left's right pairs with right's left.

Simultaneous recursion lets you compare two subtrees in lockstep. Same skeleton, two pointers, crossed recursive calls.

The Underlying Truth

All three traversals — preorder, inorder, postorder — perform the exact same walk through the tree. Every node is visited three times:

On the way down (arriving for the first time)
After the left subtree returns
After the right subtree returns

Preorder captures moment 1. Inorder captures moment 2. Postorder captures moment 3.

This isn't three different algorithms. It's one algorithm with three hooks. Once you see this, you'll never confuse the traversals again — and in Lesson 4, we'll make this explicit with the (node, state) technique.

Try It

The starter code has three functions with TODOs. Fill in each one and verify:

Preorder:  1 2 4 5 3 6 7
Inorder:   4 2 5 1 6 3 7
Postorder: 4 5 2 6 7 3 1

Predict before running: What's the preorder of a single-node tree? Just [root]. What's the postorder? Also [root]. For a single node, all three traversals are identical.

Challenge: Write bool hasPathSum(Node* root, int targetSum) that returns true if there's a root-to-leaf path whose values sum to targetSum. Is this preorder, inorder, or postorder? (Hint: you accumulate a running sum as you go down.)

Challenge 2: Given preorder [1, 2, 4, 5, 3, 6, 7] and inorder [4, 2, 5, 1, 6, 3, 7], can you reconstruct the tree? Why do you need both? (Hint: preorder tells you the root; inorder tells you what's on the left vs. right.)

Edge Cases to Watch For

Symmetric tree check with unequal structures: isMirror must handle one subtree being nullptr while the other is not — return false immediately with an explicit if guard. Dereferencing nullptr here is a crash.
Reconstructing from traversals with non-unique values: If inorder values are not unique, the split between left and right subtrees is ambiguous and reconstruction produces an incorrect tree. The algorithm requires distinct values.

Problems

Problem	Link	Difficulty
LC 144 — Binary Tree Preorder Traversal	leetcode.com/problems/binary-tree-preorder-traversal	Easy
LC 94 — Binary Tree Inorder Traversal	leetcode.com/problems/binary-tree-inorder-traversal	Easy
LC 145 — Binary Tree Postorder Traversal	leetcode.com/problems/binary-tree-postorder-traversal	Easy
LC 104 — Maximum Depth of Binary Tree	leetcode.com/problems/maximum-depth-of-binary-tree	Easy
LC 101 — Symmetric Tree	leetcode.com/problems/symmetric-tree	Easy
LC 105 — Construct Binary Tree from Preorder and Inorder	leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal	Medium