Algorithms from zero
Recursion on trees
You know three ways to walk a tree: pre-order, in-order, post-order. But walking is not solving. To solve a tree problem—find the height, count the nodes, check if it is balanced—you need to think like a tree. A tree is a node with two subtrees. So to solve for the node, ask the same question of both subtrees, then combine their answers with the node’s own value. This is recursion on trees, and it is the most powerful tool you have for tree problems.
After this lesson you can write recursive functions to solve tree problems by working bottom-up (postorder), recognize and implement the “recurse on subtrees and combine” pattern, trace a recursive tree function to verify it is correct, explain why returning a value from each subtree is the key to solving the problem, and choose the right base case (empty subtree) and combination rule for your problem.
What does “recursion on trees” mean?
Recursion on trees is a way to solve problems where you:
- Solve the problem for the left subtree (recursively).
- Solve the problem for the right subtree (recursively).
- Combine the two answers with information about the current node.
- Return the combined result up the call stack.
The key insight: a tree is just a node with two subtrees. So assume your function already works on the subtrees, and build the answer for the current node from those results.
Base case: the empty subtree
Every recursive tree function needs a base case. In tree problems, the base case is always when the subtree is null (empty). At that point, you return a value that makes sense for your problem—often 0 for counts, or -1 for heights.
Combining results: postorder thinking
The order in which you visit the tree matters. To combine results from the subtrees with the current node, you must:
- Recursively get the left result.
- Recursively get the right result.
- Combine them with the current node.
This is postorder: left subtree, right subtree, then the node itself.
The mental model
Think of the recursion as messages flowing UP the tree:
- Each leaf sends up its base-case value.
- Each internal node asks both children “what is the answer for your subtree?”, then combines the answers and sends the result up to its parent.
- The root returns the answer for the entire tree.
Example 1: Computing the height of a tree
The height of a tree is the longest path from root to any leaf.
The recursive idea: height of a node = 1 + max(height of left subtree, height of right subtree).
1
function height(node) {
2
// Base case: empty tree
3
if (node === null) return -1;
4
5
// Recursive case: ask both subtrees for their heights
6
const leftHeight = height(node.left);
7
const rightHeight = height(node.right);
8
9
// Combine: take the max and add 1
10
return 1 + Math.max(leftHeight, rightHeight);
11
}
- L1 Function computes the height of the subtree rooted at node.
- L3 Base case: an empty tree has height -1. This makes the math work: a single node's height = 1 + max(-1, -1) = 0.
- L6 Recursively ask the left subtree for its height.
- L7 Recursively ask the right subtree for its height.
- L10 Combine: the height of this node is 1 plus the taller subtree.
Example: For the tree:
1
/ \
2 3
/
4height(4)is a leaf: its two null children each return -1, so it returns 1 + max(-1, -1) = 0. Node 4 has height 0.height(2)asks for height(4) and height(null), gets 0 and -1, returns 1 + max(0, -1) = 1. Node 2 has height 1.height(3)is a leaf: returns 1 + max(-1, -1) = 0. Node 3 has height 0.height(1)asks for height(2) and height(3), gets 1 and 0, returns 1 + max(1, 0) = 2. The tree has height 2.
Example 2: Counting nodes in a tree
The count of nodes: count = 1 (for this node) + count of left subtree + count of right subtree.
1
function countNodes(node) {
2
// Base case: empty tree has 0 nodes
3
if (node === null) return 0;
4
5
// Recursive case: ask both subtrees for their node counts
6
const leftCount = countNodes(node.left);
7
const rightCount = countNodes(node.right);
8
9
// Combine: 1 (current node) + left + right
10
return 1 + leftCount + rightCount;
11
}
- L1 Function returns the number of nodes in the subtree rooted at node.
- L3 Base case: an empty tree has 0 nodes.
- L6 Recursively count nodes in the left subtree.
- L7 Recursively count nodes in the right subtree.
- L10 Combine: add 1 for the current node, plus all nodes in both subtrees.
Example: For the same tree:
countNodes(4)is a leaf: its null children each return 0, so it returns 1 + 0 + 0 = 1.countNodes(2)asks for countNodes(4) and countNodes(null), gets 1 and 0, returns 1 + 1 + 0 = 2. Subtree rooted at 2 has 2 nodes.countNodes(3)returns 1 + 0 + 0 = 1. Subtree rooted at 3 has 1 node.countNodes(1)asks for countNodes(2) and countNodes(3), gets 2 and 1, returns 1 + 2 + 1 = 4. The entire tree has 4 nodes.
Running both functions on a concrete tree
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
height(root);
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
countNodes(root);
Time complexity
Both height and countNodes visit every node in the tree exactly once. Each node is processed once: we compute the maximum (for height) or add a count (for node count) in O(1) time. For a tree with n nodes, the time complexity is O(n).
Space complexity
The space comes from the recursion call stack. In the worst case, the recursion stack depth equals the height of the tree. In a balanced tree, height is O(log n). In a skewed tree (like a linked list), height is O(n). Therefore, space complexity is O(h), where h is the height of the tree.
For a tree with structure: 5 / \ 3 7 / / \ 2 6 8 What is the height of the tree?
In the height function, why do we return -1 for a null subtree instead of 0?
For countNodes, what does each recursive call return?
When you call height on the root of a tree with height 2, which subtree is explored first?
What is the space complexity of the height function for a skewed binary tree (where every node has only a right child)?
lesson.inset.undefined
Why recursion on trees? Iterative tree solutions often require a stack or queue to track nodes you have not yet processed. Recursion does that tracking for you using the call stack. It also matches the tree’s structure: a tree is a node plus two subtrees, so the recursive structure mirrors the data structure.
lesson.inset.undefined
Empty trees and single nodes. If the root is null, the base case returns immediately. If the tree is a single node, both children are null, the recursive calls hit the base case, and you combine the base-case values with the current node. No special handling needed.
lesson.inset.undefined
Trace by hand. Draw a small tree (3–4 nodes). Pick a problem (height, count, or a simple property). Execute the recursion by hand: at each call, note the recursive calls, wait for them to return, then combine. Watch the values flow up the tree. This builds intuition.
What is the key insight that makes recursion on trees work?
Recursion on trees solves problems by asking the same question of both subtrees, combining their answers with the current node, and returning the combined result. The base case is always an empty subtree (null). The two worked examples—height and countNodes—show the pattern: assume both subtrees return a value, combine those values with information about the current node (max for height, sum for count), and return the result. Time complexity is O(n) (visit each node once). Space complexity is O(h) (recursion stack depth = tree height). This pattern extends to any tree problem: check a property, sum values, find a maximum, etc. The next lesson covers binary search trees: trees with a specific property (values in the left subtree are smaller, values in the right are larger) that lets you search in O(log n) time.