104. Maximum Depth of Binary Tree - Detailed Explanation

Given the root of a binary tree, return its maximum depth, which is the number of nodes along the longest path from the root down to the furthest leaf. An empty tree has depth zero. The recursive solution is three lines, which is why interviewers use this question as a warm-up and then immediately ask a follow-up.

This problem appears on the Blind 75 list and in LeetCode 75, where it opens the binary tree section.

Examples

Constraints

• The number of nodes is in the range 0 to 10,000.
• Each node value is between -100 and 100.

The node values never matter here. Only the shape of the tree does, which is a useful thing to say out loud in an interview.

Which pattern this problem belongs to

This is the tree depth first search pattern. Depth first search walks as deep as it can down one branch before backing up and trying the next. The pattern fits any question whose answer at a node is built from the answers of its two subtrees, which is exactly the shape here: the depth at a node is one more than the deeper of its children.

The recurring techniques are collected in the most common LeetCode patterns and covered at length in LeetCode patterns you need to know.

Approach

Recurse. If the node is null, return 0. Otherwise return 1 plus the larger of the two recursive calls.

That is the whole algorithm. The reason it is correct is worth stating precisely, because an interviewer will ask. Every root-to-leaf path passes through exactly one child of the root, so the longest path overall is the longest path through the left child or the longest through the right, whichever is greater, plus the root itself.

The recursion visits each node once and does constant work per node, so the time is O(n). The space is the recursion stack, which is O(h) where h is the height. For a balanced tree that is O(log n). For a degenerate tree that is a single chain, it is O(n), and on a 10,000 node chain a recursive solution in some languages will overflow the stack. That is the follow-up to be ready for, and the iterative version below is the answer to it.

Python code

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):
    """Recursive depth first search. O(n) time, O(h) stack."""
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def max_depth_iterative(root):
    """Level order traversal. O(n) time, O(w) space for the widest level."""
    if root is None:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

Java code

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Complexity

Common mistakes

• Returning 0 for a leaf. A leaf has depth 1. The base case is the null child, not the leaf.
• Counting edges instead of nodes. This question counts nodes, so a single node answers 1, not 0. Other tree questions count edges, so read the definition each time.
• Swapping max for min without thinking. Minimum Depth of Binary Tree is a different question, and it has a trap: a node with one null child is not a leaf, so you cannot simply swap max for min.
• Assuming the recursion is always safe. Mention the degenerate chain and offer the iterative version before the interviewer asks.

Related problems

• Minimum Depth of Binary Tree, which looks symmetric and is not, for the reason above.
• Balanced Binary Tree, which computes the same depth but compares the two sides at every node.
• Binary Tree Right Side View, which uses the level order traversal shown above rather than the recursion.

How to Prepare

• Write the three-line recursion from memory. It is the base template for a large family of tree questions, and fluency here saves time on the harder ones.
• Know the iterative version too. The stack depth follow-up is near certain on this question, and a level order traversal answers it directly.
• Learn the pattern rather than the problem. Grokking the Coding Interview teaches tree traversal as its own chapter, which makes the whole family faster to work through.