DSA With AI
Week 4 ยท Trees

Maximum Depth of Binary Tree

Return the number of nodes on the longest root-to-leaf path in a binary tree.

Easy Trees Week 4 Practice runner

Frame the problem

  • An empty tree has depth 0.
  • A one-node tree has depth 1.
  • Balanced and skewed trees use the same recurrence.
1. Reveal example inputs and outputs

Example 1

Input:

max_depth([
  3,
  [
    9,
    null,
    null
  ],
  [
    20,
    [
      15,
      null,
      null
    ],
    [
      7,
      null,
      null
    ]
  ]
])

Output:

3

Example 2

Input:

max_depth(null)

Output:

0
2. Brute force first

If a node asks each child for its depth, what single formula combines the answers?

3. Reveal the insight ladder
  1. The depth of an empty subtree is 0.
  2. The depth of a non-empty subtree is 1 for the current node plus the deeper child.
  3. Each recursive call returns a complete answer for its subtree.
  4. No global state is needed.
4. Dry run before code
  1. For tree [3, 9, 20, null, null, 15, 7], leaves 9, 15, and 7 return depth 1.
  2. Node 20 returns 1 + max(1, 1) = 2.
  3. Root 3 returns 1 + max(1, 2) = 3.
5. Reveal final Python solution 
def max_depth(root):
    if root is None:
        return 0
    value, left, right = root
    return 1 + max(max_depth(left), max_depth(right))

Complexity: Time O(n), space O(h) for recursion.

Interview narration

  • I will make depth a return value instead of mutating a global maximum.
  • The base case defines the empty-subtree contribution.
  • The recurrence is exhaustive because the deepest path must go through either the left child or the right child.

Common traps

  • Returning 1 for an empty tree.
  • Counting edges when the prompt expects nodes.
  • Using BFS level counting but forgetting to increment once per level rather than once per node.

Follow-up drills

1. How would you write the BFS version?

Use a queue seeded with the root. For each level, process exactly the current queue length, enqueue children, then increment depth once.

2. What if the interviewer asks for minimum depth?

You cannot take min(left, right) blindly when one child is missing. A leaf has minimum depth 1; if only one child exists, continue through that child.

3. What is the space difference between balanced and skewed trees?

Recursive space is O(log n) for a balanced tree and O(n) for a skewed tree.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.