← Tree Recursion · guided lesson
Tree Recursion
the story
Tree recursion (solve the children, combine)
Every tool here exists because something was too slow or broke without it. Here is what.
In his 1960 Lisp paper, McCarthy built all data from ordered pairs: an S-expression is a pair whose two parts are atoms or smaller S-expressions — a binary tree.
He then defined functions on them recursively.
His equal says two trees are equal if they are the same atom, or if their first halves are equal and their second halves are equal — the same check as LeetCode's Same Tree.
His subst rebuilds a tree from its two rebuilt halves. Every "solve left, solve right, combine" function in this chapter has that shape.
the problem it solved
Computing anything about a nested structure — equality, size, a transformed copy — with a function as short as the structure's definition.
why it matters: without it
Every subtree question would be re-asked from scratch at each ancestor — O(n²) instead of O(n) on deep trees.
sources: McCarthy — Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (CACM, 1960) ↗ · McCarthy (1960) — the section defining S-expressions, equal and subst ↗
also in this chapter: Pass information down (top-down parameters) · Return one thing, record another (global best) · Lowest common ancestor · Rebuilding a tree from traversals · Subtree ids (hash-consing): equal subtrees, equal numbers
the idea
The idea in 30 seconds
Most tree solutions are tiny recursive functions: solve the left subtree, solve the right subtree, combine with this node.
Information flows two ways: down as parameters (depth, bounds, path so far) and up as return values (height, sum, found?).
When the answer is a path that may bend at any node, return one thing to the parent and record another in a global best.
picture this
File Explorer → Properties on a folder: it can't show that projects is 2 GB until every sub-folder has reported its own size — answers flow up. A file's full path flows the other way: /home/priya hands its path down, and projects adds its own name.
watch it
Max depth — answers flow up
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Max depth — answers flow up
Calls go down to the leaves; each node's answer (↑) appears only after both children have reported.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Path sum — the target flows down
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Path sum — the target flows down
Each call subtracts its value and hands the rest (r) to its children; only a leaf may decide that a path is complete.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 12
Read it once. Say it out loud once. Bas.
The leap of faith: say what f(node) returns in one sentence, assume f(node.left) and f(node.right) already return exactly that, and only write how to combine them with node. The base case is null.
key idea 2 of 12
Read it once. Say it out loud once. Bas.
Return info up (postorder): height, size, sum, is-balanced, found-p — anything a node can only know after its children finish.
key idea 3 of 12
Read it once. Say it out loud once. Bas.
Pass info down (preorder parameters): depth, allowed range, remaining sum, max so far, the number spelled so far — anything a node already knows before visiting its children.
key idea 4 of 12
Read it once. Say it out loud once. Bas.
Ints copy, lists don't: Java passes an int by value, so remaining or max needs no undo. A shared List or HashMap is one object on the heap — add before the recursive calls, remove after (Path Sum II, III).
key idea 5 of 12
Read it once. Say it out loud once. Bas.
Root-to-leaf paths end only at a leaf: test node.left == null && node.right == null, never node == null — a node with one child is not a leaf.
key idea 6 of 12
Read it once. Say it out loud once. Bas.
Any downward path = prefix sums on the current path: the path from just below A down to X adds up to k when prefix(X) − prefix(A) = k, so a HashMap of the prefixes above X counts those paths in O(1).
key idea 7 of 12
Read it once. Say it out loud once. Bas.
Return one thing, record another: when the answer may bend at any node, return the best one-sided arm to the parent and update a global best with the two-sided bend (Diameter, Max Path Sum).
key idea 8 of 12
Read it once. Say it out loud once. Bas.
Two facts at once: return a record, an int[], or a sentinel like −1 meaning "already invalid", so the bad news travels up in O(1).
key idea 9 of 12
Read it once. Say it out loud once. Bas.
Recomputing is the classic slowdown: calling height() inside a recursion that already visits every node is O(n²) on a skewed tree. Return the height from the same pass → O(n).
key idea 10 of 12
Read it once. Say it out loud once. Bas.
Two trees in lockstep: recurse on (a.left, b.left) and (a.right, b.right) together — Same Tree; cross the pairs for a mirror (Symmetric Tree). Many subtree comparisons? Give each subtree shape an id so equal subtrees compare in O(1).
key idea 11 of 12
Read it once. Say it out loud once. Bas.
Building a tree is recursion too: preorder (from the front) or postorder (from the back) tells you the next root; inorder tells you which values go left and right of it.
key idea 12 of 12
Read it once. Say it out loud once. Bas.
Space is O(h): O(log n) when balanced, O(n) when skewed. Java has no tail-call optimization, so for 10⁵-deep chains switch to an explicit stack or parent pointers.
spot the pattern
When you see this, think this
"Maximum/minimum depth", "height", "is balanced"
Postorder: return the height up; use −1 or a record for "invalid"
"Diameter", "longest path", "any path" (doesn't have to pass the root)
Return the best one-sided arm; record the two-sided bend in a global best
"Path sum" from root to leaf, "depth of every node", "max so far on the path"
Pass the running value down as a parameter; decide at a leaf (both children null), not at null
"Return all the paths"
Backtracking: one shared list — add, recurse, remove — and save copies
+7 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Mixing up depth conventions: LeetCode's maximum depth counts nodes (one node → 1), textbook height counts edges (one node → 0). Say which one you use.
- Forgetting the
nullbase case — the first leaf crashes with aNullPointerException.
quick check
One question. No pressure.
Which traversal must compute a node's height?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Maximum Depth of Binary Tree
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
What is the "leap of faith" when writing a tree recursion?
Question 1: What is the "leap of faith" when writing a tree recursion?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.