Tree Recursion

Every tree problem asks one question at every node: what do my children know, and what must I tell my parent?

intermediate~110 min8 simulations18 problems

▶ guided lesson ⚡ 1-minute summary ↻ 15 recall cards

before this: Recursion · Traversals

Section

01 · why it exists

Why this exists, and the weight it carries

since1960

Tree recursion (solve the children, combine)

John McCarthy

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 solvedComputing anything about a nested structure — equality, size, a transformed copy — with a function as short as the structure's definition.

its jobs today

Git: a folder's tree object holds the hashes of its files and sub-folders, so hashes are computed bottom-up — a postorder over the project.
Disk usage: a folder's size is its files plus its sub-folders' sizes, computed after the children report.
Compilers and interpreters: an expression tree is evaluated or simplified bottom-up — b * c before a + b * c.

the weight it carries

Illustrative: a 10⁴-node skewed tree. Asking for every node's height from scratch costs 1 + 2 + … + 10⁴ = 50,005,000 node visits. Returning the height up from one postorder pass costs 10⁴ visits — about 5,000× less.

without it

Every subtree question would be re-asked from scratch at each ancestor — O(n²) instead of O(n) on deep trees.

when · why · how

when: A node's answer depends only on its children's answers: height, size, sum, balanced, equal, mirrored.
why: One postorder pass: O(n) time and O(h) stack. The price is recursion depth on skewed trees.
how: int f(TreeNode node) { if (node == null) return BASE; int l = f(node.left), r = f(node.right); return combine(node.val, l, r); }

since?

Pass information down (top-down parameters)

Carrying context (depth, bounds, a running total) into recursive calls as parameters is as old as recursion itself; there is no single inventor to credit.

its jobs today

CSS: inherited properties such as color flow from a parent element down to its children unless a child overrides them.
File paths: a file's full path is its folder's path plus its own name — each level hands the path down.
Validating a BST (next chapter): each node receives the (min, max) range its ancestors allow.

the weight it carries

Illustrative: the depth of every node in a 10⁶-node tree. Passing depth + 1 down: 10⁶ calls, O(1) each. Recomputing each node's depth by climbing to the root: about 10⁶ × 20 = 2·10⁷ steps when balanced, and about 5·10¹¹ on a skewed chain.

without it

Each node would have to rediscover its context (depth, path, allowed range) by climbing back up — impossible without parent links, slow with them.

when · why · how

when: A node's answer depends on its ancestors: depth, the path so far, a running sum, an allowed value range.
why: O(n) time with O(1) work per call. Copying a whole path list into every call would cost O(n) each — add before recursing and remove after instead.
how: Extra parameters on a private helper: walk(TreeNode node, int depth, …); for lists, path.add(x), recurse, then path.remove(path.size() - 1).

since?

Return one thing, record another (global best)

The "return the best arm, record the best bend" trick is standard tree dynamic programming folklore; we found no single inventor to credit.

its jobs today

Network design: in a tree-shaped network, the diameter — the longest path between two machines — is the worst-case hop count, found exactly this way.
Every "best path that may turn at some node" question — longest path, max-sum path, longest same-value path — and the tree DP problems later in the course.

the weight it carries

Illustrative: a 10⁴-node skewed tree. Trying every node as the bend and recomputing both arms: about 5·10⁷ visits. One pass that returns the arm and records the bend: 10⁴ visits.

without it

You'd need two passes or an O(n²) search, because the value the parent needs (one arm) is not the answer (the bend).

when · why · how

when: The answer is a path that can bend at any node: diameter, max path sum, longest univalue path.
why: O(n) time and O(h) space in one pass. The trick is that the returned value and the recorded value are different.
how: A field best reset in the public method (or an int[] best). The helper returns 1 + max(l, r) or node.val + max(l, r) and updates best with the two-sided value.

since1973–1984

Lowest common ancestor

Alfred Aho, John Hopcroft & Jeffrey Ullman; Dov Harel & Robert Tarjan

Aho, Hopcroft and Ullman defined the lowest common ancestor problem in 1973 (STOC; journal version 1976) and gave the first efficient algorithms. In 1984 Harel and Tarjan showed that after O(n) preprocessing, any LCA query can be answered in O(1) time. The one-pass recursion in this chapter needs no preprocessing at all: O(n) for a single query — the right tool when you ask once.

the problem it solvedFinding where two branches of a hierarchy meet — the basis of tree distances, merges and "closest shared container" questions.

its jobs today

Git: git merge-base finds the best common ancestor of two commits to use as the base of a three-way merge.
Browsers: Range.commonAncestorContainer returns the deepest DOM node that contains both ends of a selection.
Tree distances: dist(a, b) = depth(a) + depth(b) − 2 · depth(LCA(a, b)).

the weight it carries

Illustrative: a balanced tree of 10⁶ nodes (depth ≈ 20). One recursive LCA query may visit all 10⁶ nodes. With parents and depths stored once, a query climbs at most 2 × 20 = 40 steps. For 10⁵ queries: 10¹¹ visits vs 4·10⁶ steps — that's why heavy users preprocess.

without it

Merges, DOM range operations and tree distances would each need a full search to find where two branches meet.

when · why · how

when: Two nodes and the question "where do their paths from the root meet?" — merges, distances, the closest shared folder.
why: One query: O(n) time, O(h) stack, no extra memory. Many queries: preprocess (parent + depth climbing, binary lifting at O(log n) per query, or Harel–Tarjan's O(1)).
how: Recursive: return root if it is null, p or q; combine the left and right reports. Iterative: Map<TreeNode, TreeNode> parent, then climb.

since?

Rebuilding a tree from traversals

Rebuilding a tree from its preorder and inorder sequences is a classic textbook exercise; we found no single inventor to credit.

its jobs today

Deserializing: turning a flat sequence back into a tree — the same "the next token is the next root" idea as the preorder codec in Tree Traversals.
Parsers: a recursive-descent parser (javac uses one) builds the syntax tree top-down from a flat stream of tokens, each method reading the next token to decide which node to create.

the weight it carries

Illustrative: n = 3000 nodes. Searching inorder for each root costs up to 3000 × 3001 / 2 ≈ 4.5·10⁶ comparisons on a skewed tree. A HashMap of value → index makes each lookup O(1): 3000 lookups in total.

without it

Two traversals would stay just two lists; you'd need the tree's shape stored separately (or null markers) to get it back.

when · why · how

when: You have preorder (or postorder) plus inorder of a tree with unique values.
why: O(n) with a HashMap, O(n²) worst with a linear search. Inorder is required: preorder + postorder can't tell which side a lone child is on.
how: Map<Integer, Integer> indexOf, a running next index into preorder, and build(lo, hi) that builds the left subtree before the right (with postorder: walk it backwards and build the right first).

since1958–1974

Subtree ids (hash-consing): equal subtrees, equal numbers

Andrei Ershov; Eiichi Goto

In 1958 Andrei Ershov, writing about how a compiler should translate arithmetic, used hashing so the compiler could spot an expression it had already built and reuse it instead of computing it again. In 1974 Eiichi Goto built the idea into a Lisp system: before making a new pair, look it up in a hash table and hand back the existing copy if there is one. Lisp programmers call this hash consing. The payoff: two structures are equal exactly when they are the same object — a one-step check instead of a full walk. Subtree of Another Tree uses the same idea with an int id per subtree shape.

the problem it solvedSpotting repeated structure — the same subexpression, the same subtree — without comparing it node by node every time.

its jobs today

JIT compilers: HotSpot's C2 keeps a hash table of its IR nodes (NodeHash, used for value numbering), so an expression it has already built is found and reused instead of computed twice.
Git: every folder is stored as a tree object named by the hash of its contents — including its sub-folders' hashes — so identical folders get the same id and are stored once.

the weight it carries

Illustrative: root has n = 2,000 nodes and subRoot m = 1,000. Running Same Tree from every node can approach n × m = 2,000,000 node comparisons on a bad input (long chains of equal values). With ids: 3,000 HashMap lookups, then one int comparison per node.

without it

Every "is this the same subtree?" question is a fresh walk: O(m) per check, O(n·m) to test every node.

when · why · how

when: Many equality checks between subtrees: subtree matching, finding duplicate subtrees, sharing repeated structure.
why: O(n + m) expected time and O(n + m) memory, versus O(n·m) for repeated walks. Exact: the map compares whole keys, so a hash collision can never fake a match.
how: Map<String, Integer> ids; postorder key = id(left) + "," + val + "," + id(right) and id = ids.computeIfAbsent(key, k -> ids.size() + 1), with id(null) = 0.

02 · plain english

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.

03 · remember

What you must know

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.
Return info up (postorder): height, size, sum, is-balanced, found-p — anything a node can only know after its children finish.
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.
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).
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.
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).
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).
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).
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).
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).
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.
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.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Max depth — answers flow up

Calls go down to the leaves; each node's answer (↑) appears only after both children have reported.

loading simulation…

javajava.util.*

1class Solution {2    public int maxDepth(TreeNode root) {3        if (root == null) return 0;                // empty tree has depth 04        int left = maxDepth(root.left);            // ask the left subtree5        int right = maxDepth(root.right);          // ask the right subtree6        return 1 + Math.max(left, right);          // me + the deeper side7    }8}

sim

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.

loading simulation…

javajava.util.*

1class Solution {2    public boolean hasPathSum(TreeNode root, int targetSum) {3        if (root == null) return false;                       // no node, no path4        int remaining = targetSum - root.val;                 // what the rest of the path must add5        if (root.left == null && root.right == null) return remaining == 0;   // paths end only at leaves6        return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);7    }8}

sim

Invert — trust the calls, then swap

Each call mirrors both subtrees first and then swaps them, so the tree flips from the bottom up.

loading simulation…

javajava.util.*

1class Solution {2    public TreeNode invertTree(TreeNode root) {3        if (root == null) return null;4        TreeNode left = invertTree(root.left);     // mirror both subtrees first…5        TreeNode right = invertTree(root.right);6        root.left = right;                         // …then swap them7        root.right = left;8        return root;9    }10}

sim

Symmetric — two halves in lockstep

a and b walk the two halves together: outside pair first, then inside pair. One mismatch stops everything.

loading simulation…

javajava.util.*

1class Solution {2    public boolean isSymmetric(TreeNode root) {3        return root == null || isMirror(root.left, root.right);4    }5 6    /** True if subtree a is the mirror image of subtree b. */7    private boolean isMirror(TreeNode a, TreeNode b) {8        if (a == null && b == null) return true;      // both spots empty: a match9        if (a == null || b == null) return false;     // only one side has a node10        if (a.val != b.val) return false;11        return isMirror(a.left, b.right)              // the outside pair12            && isMirror(a.right, b.left);             // the inside pair13    }14}

sim

Diameter — return height, record the best bend

`sub` is the height a node returns to its parent; the glowing path is the best bend recorded so far.

loading simulation…

javajava.util.*

1class Solution {2    private int best;3 4    public int diameterOfBinaryTree(TreeNode root) {5        best = 0;6        height(root);7        return best;8    }9 10    /** Returns the height (in nodes) and updates the best path seen so far. */11    private int height(TreeNode node) {12        if (node == null) return 0;13        int left = height(node.left);14        int right = height(node.right);15        best = Math.max(best, left + right);           // path that bends here, in edges16        return 1 + Math.max(left, right);              // what my parent needs17    }18}

sim

Max path sum — drop negative arms

Same shape as Diameter, with values: an arm worth less than 0 is replaced by 0, and the bend uses both arms.

loading simulation…

javajava.util.*

1class Solution {2    private int best;3 4    public int maxPathSum(TreeNode root) {5        best = Integer.MIN_VALUE;           // values can be negative: never start at 06        gain(root);7        return best;8    }9 10    /** Best downward path starting at node; also records the best path that bends at node. */11    private int gain(TreeNode node) {12        if (node == null) return 0;13        int left = Math.max(0, gain(node.left));          // a negative branch is worse than none14        int right = Math.max(0, gain(node.right));15        best = Math.max(best, node.val + left + right);   // path bending here uses both sides16        return node.val + Math.max(left, right);          // parent can extend only ONE side17    }18}

sim

Lowest common ancestor

Every call reports what it found. The first node that hears back from *both* sides is the answer.

loading simulation…

javajava.util.*

1class Solution {2    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {3        if (root == null || root == p || root == q) return root;4        TreeNode left = lowestCommonAncestor(root.left, p, q);5        TreeNode right = lowestCommonAncestor(root.right, p, q);6        if (left != null && right != null) return root;                // p and q split here7        return left != null ? left : right;                            // pass up whatever was found8    }9}

sim

Path sum III — prefix sums on the current path

s is the sum from the root. The HashMap holds the prefixes above the current node; each one is taken back out on the way up.

loading simulation…

javajava.util.*

1class Solution {2    public int pathSum(TreeNode root, int targetSum) {3        Map<Long, Integer> seen = new HashMap<>();   // prefix sums on the current root path → how many4        seen.put(0L, 1);                             // the empty prefix: lets a path start at the root5        return walk(root, 0L, targetSum, seen);6    }7 8    private int walk(TreeNode node, long sum, int target, Map<Long, Integer> seen) {9        if (node == null) return 0;10        sum += node.val;                             // prefix sum from the root to this node11        int count = seen.getOrDefault(sum - target, 0);   // paths that END here12        seen.merge(sum, 1, Integer::sum);            // now my descendants can see me13        count += walk(node.left, sum, target, seen) + walk(node.right, sum, target, seen);14        seen.merge(sum, -1, Integer::sum);           // leaving: my siblings must not see me15        return count;16    }17}

05 · cost

Time & space, explained

Tree recursions (n nodes, height h)
	Time	Extra space	why
Height, size, sum, balanced — one postorder pass	O(n)	O(h)	Each node is visited once with O(1) work; the stack holds one root-to-node path.
Diameter / max path sum with a global best	O(n)	O(h)	Still one pass: the bend is recorded at the node, only one arm travels up.
Same pattern, but height() recomputed at every node	O(n²) worst	O(h)	Each node's height is recomputed once per ancestor: n + (n − 1) + … on a skewed tree (O(n log n) when balanced).
Same tree / mirror (two trees in lockstep)	O(min(n, m))	O(min(h₁, h₂))	Stops at the first difference; never goes deeper than the shorter tree.
Subtree: Same Tree started at every node (subRoot has m nodes)	O(n·m) worst	O(h₁ + h₂)	Up to m comparisons at each of n starting points — long chains of equal values are the bad case.
Subtree: one id per subtree shape (HashMap)	O(n + m) expected	O(n + m)	Each node builds one short key and does one O(1)-average lookup; the map stores each distinct shape once.
Path state passed down (Path Sum, Good Nodes, Sum Root to Leaf)	O(n)	O(h)	One visit per node; the state is one int per stack frame.
Path Sum II: one shared path, k matching paths copied	O(n + k·h)	O(h) + output	O(1) add/remove per node; only the k saved paths are copied, O(h) each.
Path Sum III: start a walk at every node	O(n·h)	O(h)	Each node is walked once from every ancestor: n log n balanced, n²/2 for a chain.
Path Sum III: prefix sums + HashMap with undo	O(n) average	O(n)	One O(1)-average lookup and update per node; the map keeps at most one key per node.
Count nodes of a complete tree (perfect-subtree shortcut)	O(log² n)	O(log n)	About log n levels do real work, each with an O(log n) walk down the outer edges.
Flatten to a list in place (splice under the left subtree)	O(n)	O(1)	Each node is searched as a rightmost node at most once; no recursion, no list.
Lowest common ancestor, one recursive pass	O(n)	O(h)	Each node reports at most once.
Build from preorder (or postorder) + inorder with a HashMap	O(n)	O(n)	Each node is created once with an O(1) index lookup; the map holds n entries.
Same build with a linear search for each root	O(n²) worst	O(h)	Each of n roots may scan the whole inorder range on a skewed tree.

Why recomputing hurts — n = 10⁴ nodes
	Balanced (h ≈ 13)	Skewed chain (h = n − 1)	why
Height returned up in one pass	10⁴ visits	10⁴ visits	Shape doesn't matter: every node is visited exactly once.
Height recomputed at every node	≈ n·log₂ n ≈ 1.3·10⁵	n(n + 1)/2 ≈ 5·10⁷	Each node is re-walked once per ancestor: about 13 ancestors when balanced, up to n when skewed.
Recursion depth	≈ 14 frames	10⁴ frames — risky on a small stack	Depth = height + 1; a chain makes recursion as deep as the tree is big.

06 · java

Raw vs Collections Framework

Pass info down vs return info up

javapass down (depth)java.util.*

1class PassDown {2    /** Depth flows DOWN as a parameter: a child's depth = parent's depth + 1. */3    static void depths(TreeNode node, int depth, Map<Integer, Integer> out) {4        if (node == null) return;5        out.put(node.val, depth);                 // known BEFORE visiting the children6        depths(node.left, depth + 1, out);7        depths(node.right, depth + 1, out);8    }9}

javareturn up (record Info)java.util.*

1class ReturnUp {2    /** Everything we want to know about one subtree, returned in one trip. */3    record Info(int size, int height, int sum) {}4 5    /** Height flows UP as a return value: a node needs its children's answers first. */6    static Info summarize(TreeNode node) {7        if (node == null) return new Info(0, 0, 0);   // empty tree: the base case8        Info l = summarize(node.left);9        Info r = summarize(node.right);10        return new Info(11                1 + l.size() + r.size(),12                1 + Math.max(l.height(), r.height()),13                node.val + l.sum() + r.sum());14    }15}

Depth is known before visiting a node (parent's depth + 1), so it travels down as a parameter.
Height, size and sum are known only after the children finish, so they travel up as return values — a postorder.
A Java record (Java 16+) returns several facts at once. In interviews an int[] or a field is also fine; say why you chose it.

Path state: a fresh copy per call vs one shared list

javanew ArrayList in every calljava.util.*

1class Solution {2    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {3        List<List<Integer>> result = new ArrayList<>();4        walk(root, targetSum, new ArrayList<>(), result);5        return result;6    }7 8    /** pathAbove is never changed: every call makes its own, longer copy. */9    private void walk(TreeNode node, int remaining, List<Integer> pathAbove, List<List<Integer>> result) {10        if (node == null) return;11        List<Integer> path = new ArrayList<>(pathAbove);     // O(h) copy at EVERY node12        path.add(node.val);13        remaining -= node.val;14        if (node.left == null && node.right == null && remaining == 0) result.add(path);15        walk(node.left, remaining, path, result);16        walk(node.right, remaining, path, result);17    }18}

javaone ArrayList + remove (backtracking)java.util.*

1class Solution {2    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {3        List<List<Integer>> result = new ArrayList<>();4        walk(root, targetSum, new ArrayList<>(), result);     // ONE path list, shared by every call5        return result;6    }7 8    private void walk(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> result) {9        if (node == null) return;10        path.add(node.val);                                   // choose this node11        remaining -= node.val;12        if (node.left == null && node.right == null && remaining == 0) {13            result.add(new ArrayList<>(path));                // save a COPY: path keeps changing14        } else {15            walk(node.left, remaining, path, result);16            walk(node.right, remaining, path, result);17        }18        path.remove(path.size() - 1);                         // un-choose: remove by INDEX19    }20}

Java passes an int by value: each call gets its own remaining, so a child can't spoil the parent's copy and there is nothing to undo.
A List is one object on the heap; every call holds a reference to the same one. Whatever a call adds, it removes before returning.
Save new ArrayList<>(path), not path — otherwise every saved answer is the same list, and it ends up empty.
path.remove(path.size() - 1) removes by index. On a List<Integer>, path.remove(node.val) also picks the index overload — a classic bug.

Returning two facts: a sentinel vs a record

java−1 sentineljava.util.*

1class Solution {2    private static final int UNBALANCED = -1;3 4    public boolean isBalanced(TreeNode root) {5        return check(root) != UNBALANCED;6    }7 8    /** Height of the subtree, or -1 as soon as any part of it is unbalanced. */9    private int check(TreeNode node) {10        if (node == null) return 0;11        int left = check(node.left);12        if (left == UNBALANCED) return UNBALANCED;          // stop early, pass the bad news up13        int right = check(node.right);14        if (right == UNBALANCED) return UNBALANCED;15        if (Math.abs(left - right) > 1) return UNBALANCED;16        return 1 + Math.max(left, right);17    }18}

javarecord Status(balanced, height)java.util.*

1class BalancedWithRecord {2    /** Two facts about a subtree travel up together. */3    record Status(boolean balanced, int height) {}4 5    public boolean isBalanced(TreeNode root) {6        return check(root).balanced();7    }8 9    private Status check(TreeNode node) {10        if (node == null) return new Status(true, 0);11        Status l = check(node.left);12        if (!l.balanced()) return l;              // bad news travels straight up13        Status r = check(node.right);14        if (!r.balanced()) return r;15        boolean ok = Math.abs(l.height() - r.height()) <= 1;16        return new Status(ok, 1 + Math.max(l.height(), r.height()));17    }18}

The sentinel packs "unbalanced" into an impossible height (−1). Short, fast, and the usual interview answer — name the constant so it isn't magic.
The record says what it means: Status(boolean balanced, int height). A little more code, much easier to read six months later.
Both stop early: once a subtree is bad, the bad news goes straight up without checking the other side.

A field for the global best

javafield best, reset per calljava.util.*

1class Solution {2    private int best;3 4    public int diameterOfBinaryTree(TreeNode root) {5        best = 0;6        height(root);7        return best;8    }9 10    /** Returns the height (in nodes) and updates the best path seen so far. */11    private int height(TreeNode node) {12        if (node == null) return 0;13        int left = height(node.left);14        int right = height(node.right);15        best = Math.max(best, left + right);           // path that bends here, in edges16        return 1 + Math.max(left, right);              // what my parent needs17    }18}

The helper returns what the parent needs (height); the field records the answer (best bend). Mixing them up is the classic bug.
Reset the field at the start of the public method, so calling it twice on one object still works.
Prefer no fields? Pass an int[] best = {0} into the helper, or return a record of (height, best).

Deep trees: recursion vs an explicit stack

javarecursivejava.util.*

1class Solution {2    public int maxDepth(TreeNode root) {3        if (root == null) return 0;                // empty tree has depth 04        int left = maxDepth(root.left);            // ask the left subtree5        int right = maxDepth(root.right);          // ask the right subtree6        return 1 + Math.max(left, right);          // me + the deeper side7    }8}

javaArrayDeque of (node, depth)java.util.*

1class Solution {2    public int maxDepth(TreeNode root) {3        if (root == null) return 0;4        Deque<TreeNode> nodes = new ArrayDeque<>();5        Deque<Integer> depths = new ArrayDeque<>();   // depth of the node at the same position6        nodes.push(root);7        depths.push(1);8        int best = 0;9        while (!nodes.isEmpty()) {10            TreeNode node = nodes.pop();11            int depth = depths.pop();12            best = Math.max(best, depth);13            if (node.left != null) { nodes.push(node.left); depths.push(depth + 1); }14            if (node.right != null) { nodes.push(node.right); depths.push(depth + 1); }15        }16        return best;17    }18}

Recursion depth = tree height. A 10⁵-node chain can overflow a default Java thread stack; ArrayDeque lives on the heap.
To make a postorder iterative you need to know when both children are done — often easier to switch to BFS or to carry state (like depth) with each node.
Java never turns recursion into a loop for you (no tail-call optimization).

Java API you will actually use
call	does	cost
`record Info(int size, int height) {}`	Return several values from one recursive call	O(1)
`Math.max(l, r) / Math.abs(l - r)`	Combine the children's answers	O(1)
`Integer.MIN_VALUE`	Starting value for a max when values can be negative	—
`int[] best = {Integer.MIN_VALUE}`	A mutable holder instead of a field	O(1)
`Map<Integer, Integer> indexOf = new HashMap<>()`	Value → inorder index when rebuilding a tree	O(1) average
`Map<TreeNode, TreeNode> parent`	Parent pointers for an iterative LCA	O(1) average
`a == b on TreeNode`	Compare nodes by reference (LCA's p and q)	O(1)
`Deque<TreeNode> stack = new ArrayDeque<>()`	Explicit stack when the tree may be very deep	O(1) amortized
`path.remove(path.size() - 1)`	Undo the last add on the way back (by index)	O(1)
`result.add(new ArrayList<>(path))`	Save a snapshot of the current path	O(h)
`seen.merge(sum, 1, Integer::sum)`	Count a prefix sum; merge with −1 to take it back	O(1) average
`ids.computeIfAbsent(key, k -> ids.size() + 1)`	Give a new subtree shape the next id, or return the old one	O(1) average
`(1 << h) - 1`	Nodes in a perfect tree with h levels	O(1)

A node's answer depends on its children (height, balanced, sum)

→ Postorder: return info up

Children finish before the parent combines their results.

A node's answer depends on its ancestors (depth, bounds, path so far)

→ Preorder: pass info down as parameters

The parent knows it before the child runs.

The best path may bend at any node

→ Return one arm, update a global best

A parent can extend only one side; the bend is complete at this node.

Two facts from one subtree

→ A record, an int[], or a sentinel

One pass instead of two.

Compare or mirror two trees

→ Recursion on pairs of nodes

Both trees are walked together, stopping at the first difference.

Record every root-to-leaf path that works

→ One shared List: add, recurse, remove; copy at a match

O(1) per step instead of copying the path at every node.

Count downward paths with sum k (any start, any end)

→ Prefix sums of the current path in a HashMap<Long, Integer>, undone on return

O(n) instead of starting a fresh walk at every node.

Many "is this subtree equal to that one?" checks

→ An id per subtree shape: (left id, value, right id) in a HashMap

Each check becomes one int comparison.

Rebuild a tree from preorder (or postorder) + inorder

→ Running index into preorder (or backwards through postorder) + HashMap of inorder positions

O(1) to find where each root splits its range.

Depth may reach 10⁵

→ Explicit ArrayDeque stack, BFS, or a parent map

Heap memory instead of the thread stack.

07 · recognise

Spot the pattern

"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

"Number of paths" that may start and end anywhere, going down

Prefix sums on the current path + HashMap seeded with {0: 1}; undo when leaving a node

"Complete tree", "count the nodes in less than O(n)"

Compare the leftmost and rightmost depths; equal → perfect → 2^h − 1

"Flatten" a tree into a list "in place"

Preorder rewiring: hang the right subtree under the left subtree's rightmost node

"Ancestor", "where do p and q meet"

Recursive LCA: return what you found; the split point is the answer

"Same", "mirror", "symmetric", "subtree of" another tree

Walk both trees in lockstep with one recursion

"Construct / rebuild" from traversals

Preorder from the front (or postorder from the back) gives the roots; inorder (via a HashMap) gives the left/right split

Deep tree (n up to 10⁵) and Java recursion

Mention StackOverflow risk; offer an iterative version

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

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 null base case — the first leaf crashes with a NullPointerException.
Returning the global answer instead of what the parent needs (e.g. returning the diameter instead of the height) — the recursion then combines the wrong things.
Starting a max at 0 when values can be negative (Max Path Sum on [-3] must return −3). Start at Integer.MIN_VALUE.
Comparing node values when the problem gives node references (LCA): compare with == on references.
Calling height() inside a recursion that already visits every node — O(n²) on a skewed tree.
Invert: root.left = invertTree(root.right); root.right = invertTree(root.left); — the second line reads the left side you just overwrote. Save one side first.
Construct from preorder + inorder: building the right subtree before the left with a running preorder index — the tokens no longer line up.
A field used as the global best but not reset in the public method: the second call starts from the first call's answer.
Checking a root-to-leaf condition at null instead of at a leaf: a node with one child is not a leaf (Path Sum on [1,2] with target 1 must be false).
Saving path itself instead of new ArrayList<>(path), or undoing with path.remove(node.val) — on a List<Integer> that removes by index.
Path Sum III with int sums (values reach 10⁹), or without undoing the prefix count on the way back — sibling branches then share prefixes.

tricks

Practise in families (the problems below follow this order): return-up summaries (Depth, Balanced) → compare or mirror (Same, Invert, Symmetric, Subtree) → path state down (Path Sum I and II, Sum Root to Leaf) → counting (Good Nodes, Complete Tree, Path Sum III) → global best (Diameter, Max Path Sum) → LCA → build or reshape (two Constructs, Flatten).
Before coding, say the function's contract in one sentence: "height(node) returns the number of nodes on the longest downward path." Then the code writes itself.
Chalo, dry-run karte hain — on a 5–7 node tree with one leaf, one node with only a left child, and the root. That covers almost every bug.
Edge cases to test every time: empty tree, single node, completely left-skewed, completely right-skewed, negative values.
Need two facts from a subtree (height and balanced)? Return both — a record, an int[], or a sentinel like −1.
State space as O(h), then explain: O(log n) if balanced, O(n) if skewed. Interviewers listen for this.
When the answer can bend, write two comments before the code: // returns: … and // records: …. They are never the same thing.

09 · why & how

Questions you might be too shy to ask

How do I "think recursively" about trees without getting lost?

Don't trace the whole recursion in your head. Trust that the call on a child returns the right answer for that child's subtree (the leap of faith). Then only answer two questions: what is the answer for null, and how do I combine my two children's answers with my own value?

What exactly is f(node.left) giving me?

The answer for the subtree that starts at node.left — not for the whole tree. height(node.left) is the height of just the left part, as if node.left were the root of its own small tree. Only at the top does it become the real answer: height(root) is the whole tree's height. Write that meaning as a comment above the method (// returns: height of the subtree at node) and every line gets easier.

What should my function return for null?

Whatever makes your combine line correct without special cases. Height counted in nodes → 0. Sum or count → 0. "Are these equal / balanced?" → true. LCA → null ("found nothing here"). Max Path Sum's arm → 0 (an empty arm adds nothing). Check it on a single node: 1 + max(0, 0) = 1. Sahi aaya? Then your base case is right.

Two recursive calls per node — isn't that exponential like Fibonacci?

No. Fibonacci's two calls overlap: fib(5) and fib(4) both recompute fib(3), again and again. In a tree, the two calls go to two different subtrees, which share no nodes. So every node gets exactly one call (plus one quick call per empty null child): about 2n calls → O(n) total, as long as each call does O(1) work.

I return true deep inside the recursion — why does the root still return false?

A return only goes back to the one call that called it, not to the top. That parent must pass the news along: return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);. If the parent just calls hasPathSum(root.left, remaining); and ignores the result, the true is lost. Rule: whenever a call returns something you need, use its value.

How do I decide whether data flows down or up?

Ask: can this node know it before looking at its children? Depth, the path so far, an allowed range — yes, so pass them down as parameters. Height, size, "did I find p?" — no, the children must answer first, so return them up.

When do I need a separate helper method?

When the method LeetCode gives you can't carry what you need. Need an extra parameter (depth, remaining sum, max so far)? Write dfs(node, depth) and call it from the given method. Need to return something different from the final answer? Diameter's helper returns a height, while diameterOfBinaryTree returns the best bend. If neither is true (Max Depth, Invert, Same Tree), just recurse on the given method itself.

Is a global variable (field) in a recursive solution bad style?

It's normal and accepted in interviews for "best so far" answers (Diameter, Max Path Sum). Reset it at the start of the public method so repeated calls work. If you prefer, pass an int[] best or return a record instead.

Why does remaining need no undo, but path does?

Java passes primitives by value: each call gets its own copy of remaining, so a child's change can't leak back to the parent. A List is an object — every call holds a reference to the same one on the heap. So whatever a call adds, it must remove before returning, or the parent and its other children see a wrong path.

Path Sum III: why put 0 in the map before starting?

The map answers "how many prefixes above me equal sum − target?". A path that starts at the root has nothing above it — the prefix before it is the empty sum, 0. Seeding {0: 1} counts those paths too. Subarray Sum Equals K does exactly the same on an array.

Why does Diameter return the height but record left + right?

Because the parent and the answer want different things. The parent can only extend the path through one child, so it needs the longest single arm (the height). The path that bends at this node uses both arms — that's a candidate answer, so it goes into best, not up.

Why can LCA return as soon as it sees p, without looking below p?

Because both nodes are guaranteed to be in the tree. If q is below p, then p is the answer anyway; if q is elsewhere, another branch will report q and the split point is higher up. (If p or q might be missing — LC 1644 — you must search the whole tree.)

Which pairs of traversals can rebuild a tree?

Preorder + inorder, or postorder + inorder, with unique values. Preorder + postorder cannot in general: if a node has a single child, nothing tells you whether it's the left or the right one.

How deep can my recursion go in Java before it breaks?

It depends on the thread's stack size and each frame's size — typically thousands to tens of thousands of calls. Balanced trees are fine (a million nodes is only ~20 deep). Skewed trees with 10⁵ nodes can throw StackOverflowError; say so and offer an iterative version.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#104
Maximum Depth of Binary Treemust-do
EasyLinkedInMicrosoftAppleBloombergUber+1
#110
Balanced Binary Tree
EasyBloombergAmazonMicrosoftMetaGoogle
#100
Same Tree
EasyBloombergAmazonGoogleMicrosoftMeta+1
#226
Invert Binary Treemust-do
EasyGoogleAmazonBloombergMicrosoftMeta+1
#101
Symmetric Treemust-do
EasyLinkedInBloombergMicrosoftAmazonGoogle+1
#572
Subtree of Another Treemust-do
EasyMetaAmazonGoogleMicrosoft
#112
Path Sum
EasyMicrosoftAmazonBloombergMeta
#113
Path Sum IImust-do
MediumBloombergMicrosoftMetaAmazon
#129
Sum Root to Leaf Numbers
MediumMetaGoogleAmazonMicrosoft
#1448
Count Good Nodes in Binary Treemust-do
MediumMicrosoftAmazonGoogle
#222
Count Complete Tree Nodes
MediumGoogleMicrosoftBloombergAmazon
#437
Path Sum IIImust-do
MediumAmazonGoogleMicrosoftMeta
#543
Diameter of Binary Treemust-do
EasyMetaAmazonOracleBloombergGoogle+1
#124
Binary Tree Maximum Path Summust-do
HardAdobeAmazonByteDance / TikTokSalesforceMeta+1
#236
Lowest Common Ancestor of a Binary Treemust-do
MediumMetaAtlassianAmazonAdobeLinkedIn+1
#105
Construct Binary Tree from Preorder and Inorder Traversal
MediumByteDance / TikTokAdobeBloombergAmazonMicrosoft+1
#106
Construct Binary Tree from Inorder and Postorder Traversal
MediumWalmartMicrosoftAmazonGoogleBloomberg
#114
Flatten Binary Tree to Linked List
MediumMicrosoftAmazonMetaGoogle

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#98
Validate Binary Search Tree
Mediumin BST
Pass info down: each node receives the (min, max) range its ancestors allow.
#427
Construct Quad Tree
Mediumin Recursion
Trust four recursive calls instead of two, then decide at the parent whether the children merge.

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
Tree recursion: f(node) = combine(f(left), f(right), node). Trust the child calls; write only the base case and the combine step.
use it when
Children's answers needed (height, balanced, count) → return up. Ancestors' context needed (depth, remaining sum, max so far) → pass down.
template
int f(TreeNode n) { if (n == null) return 0; int l = f(n.left), r = f(n.right); best = Math.max(best, l + r); return 1 + Math.max(l, r); }
cost
One pass: O(n) time, O(h) stack — about 20 frames for a balanced 10⁶-node tree, 10⁶ for a chain. Recomputing height per node: O(n²).
trap
Returning the answer instead of what the parent needs: Diameter returns the height and records left + right — never returns the bend.
trap
Paths end only at a leaf (left == null && right == null), never at null. Save new ArrayList<>(path), then path.remove(path.size() - 1).
trap
best = 0 with negative values: Max Path Sum on [-3] must give −3. Start at Integer.MIN_VALUE, reset it in the public method.
pro tip
Any downward path sums to k: prefix sums of the current path in a HashMap seeded {0: 1}; look up sum − k, add sum, recurse, take it back out.
pro tip
LCA: return root if it's null, p or q; if both sides report something, root is the split point.
pro tip
Rebuild: next preorder value (or postorder from the back) = root; a HashMap of inorder positions splits left/right; build left first (right first for postorder).

12 · recall

Flip, remember, repeat

card 1 / 15

recall

What is the "leap of faith" when writing a tree recursion?

tap or Space to flip ↻

Question 1: What is the "leap of faith" when writing a tree recursion?

13 · check yourself

Quick quiz

Which traversal must compute a node's height?
In Diameter of Binary Tree, what should `height(node)` return to its parent?
Max Path Sum: what should `best` start at?
Which of these is naturally passed DOWN as a parameter?
Checking balance by calling `height()` at every node costs what on a skewed tree of n nodes?
Recursive LCA returns as soon as `root == p`. Why is that safe here?
Construct from preorder + inorder with a running preorder index: why build the left subtree first?
A tree has 7 nodes. What's the smallest possible height (in edges)?
Symmetric Tree: after checking a.val == b.val, which calls come next?
Path Sum with `if (root == null) return targetSum == 0;` — what does it return for [1,2] with target 1?
Path Sum II saves matches with `result.add(path)` (no copy). With two matching paths, what comes back?
Path Sum III: why seed the HashMap with {0: 1}?
Count Complete Tree Nodes: the leftmost and rightmost paths both have 4 nodes. How many nodes does the tree have?

0/0 correct · 13 left

14 · learn more