Maximum Depth of Binary Tree

PracticeNeetCode ↗LeetCode ↗

Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from the root down to a leaf.

Example

Key Pointers

• The depth of a tree is 1 + the deeper of its two subtrees' depths.
• An empty subtree has depth 0 — that's the recursion's base case.
• This "combine the children's results" shape recurs across most tree problems.

Step-by-Step Analysis

1. Base case: if root is None, return 0.
2. Recursively compute the left subtree's depth and the right subtree's depth.
3. Return 1 + max(left depth, right depth).

Complexity

Time: O(n) — Space: O(h)

Code

def maxDepth(root: TreeNode | None) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

Code Explanation

How the solution above works, piece by piece.

1. An empty tree has depth 0: that's the base case.
2. A node's depth is 1 (itself) plus the depth of its deeper subtree.
3. The recursion reaches the leaves first, so values are built from the bottom up.
4. O(n) time, visiting each node once; O(height) stack, which is O(n) for a completely lopsided tree.

Visual Walkthrough

Running it on root = [3, 9, 20, null, null, 15, 7]:

Video Explanation

NeetCode — 3 Solutions, LeetCode 104