The problem asks the machine to report the length of the longest path from the root down to any leaf, counting nodes. The depth of a node is defined recursively: a null node has depth 0, and any other node has depth 1 plus the maximum depth of its two children.
That recursion is the entire solution. The machine never needs to know global state — each call only asks "how deep is this subtree?" and combines the answer from its children. This is a clean post-order traversal where the result propagates upward.
The approach is three lines of logic. First, if the node is null, return 0. Second, compute the depth of the left subtree and the right subtree with two recursive calls. Third, return 1 plus the larger of the two values. Because every node is visited exactly once, time is O(n). Space is O(h) for the recursion stack — O(log n) on a balanced tree, O(n) on a skewed tree that degenerates into a linked list.
The trickiest edge case is the empty tree, which has depth 0, not 1. A common mistake is counting edges instead of nodes, which would make a single-node tree report 0. The base case plus the "+1 for the current node" step keep the node-counting definition consistent, so a root-only tree correctly returns 1.
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))