Recursion Patterns

Bottom-Up

Each node asks its children for their answers, then combines them. Example: 'What's the height of this tree?' — each node returns 1 + max(left height, right height). The recursion builds the answer from leaves up.

O(n)

O(h)

How It Works

Bottom-up recursion computes each node's answer from its children's answers, making it a post-order pattern: recurse left, recurse right, combine. The base case handles null (or a leaf), and each level returns a small summary — a height, a subtree sum, a validity flag — that the parent folds into its own result. Height, for example, is 1 + max(left, right); balanced-tree checks return both a height and an is-balanced boolean in one pass.

The efficiency win comes from computing each subtree's summary exactly once. A naive approach that calls a separate height() inside every node's check re-walks subtrees and costs O(n^2) on skewed trees; the bottom-up version returns the height alongside the verdict and stays O(n) with O(h) stack space. Most classic tree problems — diameter, LCA, subtree sums, balance — are bottom-up at heart.

Step-by-Step Visualization

Bottom-up: compute max depth

Node 9leaf → depth 1

1/4

Code

Java

static int maxDepth(TreeNode root) {
  if (root == null) return 0;

  int left = maxDepth(root.left);
  int right = maxDepth(root.right);

  return 1 + Math.max(left, right);
}

// Children return their depths, parent adds 1

Tips & Gotchas

1Children compute and return their answers to the parent

2Parent combines children's answers to form its own answer

3Good for aggregation: height, size, balance check

Practice Problems

1Maximum Depth of Binary Tree
2Balanced Binary Tree
3Diameter of Binary Tree
4Lowest Common Ancestor of a Binary Tree
5House Robber III

About the Recursion Patterns Pattern

Most tree solutions follow one of two patterns: pass information DOWN from parent to children (top-down), or collect information UP from children to parent (bottom-up). Recognizing which to use is half the battle.

Key insight

Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.

Common Trees Interview Problems

Maximum Depth of Binary Tree
Validate BST
Binary Tree Level Order Traversal
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Diameter of Binary Tree

Frequently Asked Questions

Why does returning extra data from the recursion often improve complexity?

It avoids recomputation. If a parent needs both a child's height and its validity, returning them together means each subtree is traversed once, keeping the whole algorithm O(n). Calling separate helper functions per node can re-traverse subtrees and blow up to O(n^2).

What should the null base case return?

The identity value for your combining operation: 0 for heights and counts, true for validity checks, negative infinity for maximum path gains. Getting the base case right lets the recursive case stay uniform without special-casing leaves.