Patternwise

Tree DFS (Recursion)

Trust children to answer; combine their answers on the way up.

Brute force
O(n²) — recompute heights from every node (e.g. naive balanced check)
With the pattern
O(n) — each node visited once
Extra space
O(h) — recursion stack (O(n) worst case for a skewed tree)

In plain English

“A manager wants to know the longest chain of command below them. Instead of walking every path, they ask each direct report, "how deep is your team?", and each report asks their reports the same thing. Answers bubble back up, and the manager just takes the bigger number and adds one for themselves.”

Why it's fast

Most tree questions are 'combine answers from the left subtree and the right subtree'. With post-order recursion, each call returns a small summary (depth, height, sum, is-valid) and the parent computes its own in O(1). Each node is visited once — O(n) — instead of recomputing subtree facts repeatedly from every ancestor.

Spot it when the problem says…

  • maximum depth / height
  • diameter / longest path
  • path sum from root to leaf
  • validate a BST
  • lowest common ancestor
  • is the tree balanced / symmetric

Visualize

Max depth — answers flow back up

Return the number of nodes on the longest root-to-leaf path.

831016144713

call stack (bottom → top)

bottommax_depth(8)← top
01/37

Call max_depth(8). Can't answer yet — first ask both children.

pythonline 2
1def max_depth(node):2    if not node:3        return 04    left = max_depth(node.left)5    right = max_depth(node.right)6    return 1 + max(left, right)

variables

node
8

How to apply it

  1. 01Write the base case: what does None return? (0, True, empty, -inf…)
  2. 02Recurse on node.left and node.right and trust the results.
  3. 03Combine them into this node's answer and return it.
  4. 04If the global answer differs from what you return (diameter, max path), update a nonlocal best on the side.

Variations you'll meet

Post-order return value (max depth)

The visualizer's example.

python
def max_depth(root) -> int:    if not root:        return 0    left = max_depth(root.left)    right = max_depth(root.right)    return 1 + max(left, right)

Return one thing, track another (diameter)

Return height to the parent, but update the best diameter left + right at every node.

python
def diameter_of_binary_tree(root) -> int:    best = 0    def height(node) -> int:        nonlocal best        if not node:            return 0        l, r = height(node.left), height(node.right)        best = max(best, l + r)       # path through node        return 1 + max(l, r)    height(root)    return best

Pre-order with passed-down state

Pass bounds or running sums down (validate BST with (lo, hi), path sum with remaining target).

Backtracking on paths

Append node to path, recurse, then path.pop() — Path Sum II, Binary Tree Paths.

Common mistakes

  • Validating a BST by only comparing a node with its direct children instead of passing down bounds.
  • Treating a node with one child as a leaf in min-depth / path-sum problems.
  • Returning the global answer (diameter) instead of the local one (height) to the parent.
  • Hitting Python's recursion limit on very deep skewed trees — consider an iterative stack.

Practice ladder

Easy → hard. Tick them off as you go.

0/8 solved
  1. 01Maximum Depth of Binary Tree ↗Easy
  2. 02Invert Binary Tree ↗Easy
  3. 03Diameter of Binary Tree ↗Easy
  4. 04Balanced Binary Tree ↗Easy
  5. 05Validate Binary Search Tree ↗Medium
  6. 06Lowest Common Ancestor of a Binary Tree ↗Medium
  7. 07Path Sum II ↗Medium
  8. 08Binary Tree Maximum Path Sum ↗Hard

Think you've got it?

Let the AI interviewer throw a Tree DFS (Recursion) problem at you and grade how you explain it.

Mock interview