Maximum Depth of Binary Tree — Solution

Problem

Given a binary tree, return the number of nodes along the longest path from the root down to any leaf. A leaf is a node with no children.

[3,9,20,null,null,15,7]

• Input: root = [3, 9, 20, null, null, 15, 7]
• Output: 3
• Explanation: The longest path is 3 → 20 → 15 (or 3 → 20 → 7), passing through 3 nodes.

Intuition

The depth of a tree equals the depth of its deeper subtree, plus one to count the current node. This recursive definition maps directly to code: ask each subtree for its depth, take the larger answer, and add 1. An empty node has depth 0, which is the natural base case that terminates the recursion.

Solution — Recursive DFS

Work bottom-up: null nodes return 0, leaf nodes return 1, and every internal node returns the greater of its children's depths plus 1.

1. If the node is null, return 0 — an empty tree has no nodes.
2. Recursively compute the depth of the left subtree.
3. Recursively compute the depth of the right subtree.
4. Return the larger depth plus 1 (the current node counts as one level).

1def maxDepth(self, root: Optional[TreeNode]) -> int:
2    if root is None:
3        return 0
4    left_depth = self.maxDepth(root.left)
5    right_depth = self.maxDepth(root.right)
6    return max(left_depth, right_depth) + 1

Time: O(n) — every node is visited exactly once.

Space: O(h) — the call stack goes as deep as the tree's height; O(log n) for a balanced tree, O(n) for a completely skewed one.

Complexity Summary

Common Mistakes

• Forgetting the + 1 — returning max(left_depth, right_depth) without adding 1 gives a depth one less than the correct answer for every node in the tree.
• Skipping the null check — omitting the base case crashes when visiting a node whose child is absent, which happens with any non-perfect tree.
• Counting edges instead of nodes — the problem measures depth in nodes, so the root alone has depth 1. Returning 0 at a leaf (treating depth as edge count) produces an answer that is off by one.
• Conflating minimum depth with maximum — for minimum depth you cannot simply replace max with min, because a node with one null child is not a leaf; that variant requires extra handling to skip the null branch.
• Mixing up BFS level-counting — if you switch to an iterative BFS, increment the depth counter once per completed level (after draining the entire queue for that level), not once per dequeued node.

Related Problems

• minimum-depth-of-binary-tree — same traversal structure, but stops at the first leaf and must skip one-sided internal nodes
• diameter-of-binary-tree — computes subtree depths as a building block to find the longest path through any node
• balanced-binary-tree — verifies that no node's left and right subtree depths differ by more than 1
• binary-tree-level-order-traversal — BFS approach that counts levels naturally, a useful contrast to the recursive depth computation here
• symmetric-tree — recursive left/right mirroring check that follows the same "ask both subtrees, combine answers" shape