roadmap/trees/Maximum Depth of Binary Tree

Maximum Depth of Binary Tree

EasyAmazonGoogleLinkedInMeta

Problem

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

Intuition — the key insight

The depth of a node = 1 + max(depth of left subtree, depth of right subtree). Base case: null node has depth 0. This naturally recurses to the deepest leaf.

Approach

Recursive DFS

If root is null, return 0. Return 1 + max(maxDepth(root.left), maxDepth(root.right)).

Complexity

Time

O(n)

Space

O(h) where h=height

Every node visited once. Stack depth equals tree height — O(log n) balanced, O(n) skewed.

Solution code

Python

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

Edge cases to remember

⚠Empty tree: return 0

⚠Single node: return 1

⚠Skewed tree: O(n) recursion depth

Hints

What pattern do you think this problem uses?