Thinking Recursively on Trees
The template behind most tree problems: solve for the children, then combine - depth, node counts, and 'is this balanced?' all follow one shape.
On this page
Once you see it, most tree problems collapse into a single template: solve the problem for the children, then combine their answers for the current node. This is postorder thinking, and it turns intimidating problems - height, balance, diameter, subtree sums - into three or four lines of recursion.
The template: trust the recursion
The mental trick is to assume the recursive call already works for the subtrees, and only figure out how to combine those results at the current node. Computing a tree's height is the canonical example:
// height = longest path from this node down to a leaf
int height(TreeNode n) {
if (n == null) return 0; // base case
int left = height(n.left); // trust: left subtree's height
int right = height(n.right); // trust: right subtree's height
return 1 + Math.max(left, right); // combine
}You don't trace the whole recursion in your head - you trust that height(n.left) returns the correct
height of the left subtree, and just decide the combine step: this node's height is one more than the
taller child. Every postorder tree problem has this shape:
- Base case - what to return for a null node (usually 0, null, or true).
- Recurse on the left and right children.
- Combine their results into this node's answer.
Carrying extra information
Some problems need more than a single number returned - "is this tree balanced?" needs both the height and a balance flag. A clean approach returns a small result object, or uses a sentinel value to signal failure up the recursion:
// is the tree height-balanced? use -1 as a sentinel for "unbalanced"
int check(TreeNode n) {
if (n == null) return 0;
int left = check(n.left);
if (left == -1) return -1; // short-circuit: left already unbalanced
int right = check(n.right);
if (right == -1) return -1;
if (Math.abs(left - right) > 1) return -1; // this node violates balance
return 1 + Math.max(left, right); // otherwise return height
}
boolean isBalanced(TreeNode root) { return check(root) != -1; }Notice this computes height and checks balance in a single postorder pass - O(n) - instead of recomputing height at every node (which would be O(n²)). Combining a check with the value you're already computing is a common optimization.
Return the right thing from the recursion
The art of tree recursion is choosing what each call returns. For height, a number. For balance, a number that doubles as a flag (-1). For 'sum of all subtree sums' or lowest common ancestor, a node or a richer object. Ask: 'what does my parent need to know from me?' - and return exactly that.
A general asks each colonel "how deep does your branch of the operation go?" Rather than personally inspecting every soldier, the general trusts each colonel to report their branch's depth accurately - and each colonel got that number by asking their majors the same question, and so on down to the privates (the leaves). Every level does one small combine - "my depth is one more than my deepest subordinate's" - and the whole answer assembles itself from the bottom up. Tree recursion is exactly this delegation: trust the children's reports, combine them, pass yours up.
The maximum depth of a tree is straightforward postorder. The diameter (longest path between any two nodes, which may not pass through the root) is trickier. Explain how you'd compute the diameter in one O(n) pass, reusing the height recursion.
What is the core template for most binary-tree problems?
Key takeaways
- Most tree problems follow one template: solve for the children, then combine their results at the current node (postorder).
- Trust the recursion - assume the child calls return correct answers, and focus only on the combine step.
- Every such solution has a base case (null node), two recursive calls, and a combine.
- Return exactly what the parent needs; use richer return values or sentinels (like -1) to carry extra info.
- Computing a check alongside a value in one pass (e.g. balance with height) avoids O(n^2) recomputation.