Skip to main content
Recursion Patterns

Top-Down

Pass accumulated state from parent to child as a parameter. Example: 'Is this a valid BST?' — pass the allowed min/max range down. Each child checks itself and narrows the range for its children.

O(n)
·
O(h)

How It Works

Top-down recursion pushes information from parent to child through function parameters, acting like a pre-order walk that accumulates context on the way down. Each call receives everything its ancestors decided — a running path sum, the allowed value range for a BST, the current depth — checks or updates that state, and passes a refined version to its children. Answers are typically recorded at leaves or whenever a condition triggers, rather than assembled on the way back up.

This mirrors how you'd validate constraints that flow downward: a node's legality often depends on all its ancestors, and parameters carry that ancestry in O(1) per call. Time is O(n) since each node is visited once, and space is O(h) for the call stack. Choose top-down when a node's answer depends on the path above it; choose bottom-up when it depends on the subtree below.

Step-by-Step Visualization

Top-down: validate BST by passing range
5
0
3
1
7
2
1
3
4
4
Range(-∞, ∞)
5 valid?Yes
1/3

Code

Java
static boolean isValidBST(TreeNode root) {
  return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

static boolean isValidBST(TreeNode root, long min, long max) {
  if (root == null) return true;
  if (root.val <= min || root.val >= max) return false;

  return isValidBST(root.left, min, root.val) &&
         isValidBST(root.right, root.val, max);
}

// Pass allowed range [min, max] down to children

Tips & Gotchas

1Pass accumulated state from parent to children as parameters
2Good for path-based problems (is valid BST, root-to-leaf paths)
3The parent provides context the child needs

Practice Problems

  • 1Path Sum
  • 2Validate Binary Search Tree
  • 3Maximum Depth of Binary Tree
  • 4Sum Root to Leaf Numbers
  • 5Count Good Nodes in Binary Tree

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

How do I decide between top-down and bottom-up for a tree problem?

Ask what a single node needs to compute its answer. If it needs ancestor context — path so far, depth, inherited bounds — pass it down as parameters (top-down). If it needs subtree results — heights, sums, counts from below — return them up (bottom-up). Some problems, like path sums through arbitrary nodes, combine both.

What is a common bug when accumulating state on the way down?

Mutating a shared object, like a path list, without undoing the change when the call returns. Either pass immutable values (new sums, new bounds) or explicitly pop your addition after recursing, backtracking-style, so sibling branches see clean state.