Maximum Depth of Binary Tree

Why it belongs on this sheet

This is the easiest tree recurrence and the fastest way to warm up before deeper tree questions.

Pattern

Height from children

Approach

The depth of a tree is 1 + max(left depth, right depth). Use recursion and return 0 for a null node.

Java solution

class Solution {
  public int maxDepth(TreeNode root) {
    if (root == null) {
      return 0;
    }

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

Complexity

• Time: O(n)
• Space: O(h) recursion stack

Interview note

Say what the function returns for each node before writing code. That keeps recursion grounded.