LeetCode #104 Easy

Maximum Depth of Binary Tree

Return the maximum depth of a binary tree — the number of nodes on the longest path from the root down to a leaf.

binary treedfsrecursion

02

Intuition

Ask each child how deep its subtree is, take the bigger answer, and add one for yourself. An empty tree is depth 0 — that base case plus one line of recursion is the whole solution.

How to spot this pattern

The purest bottom-up recursion: a node's depth is one more than the deeper of its two subtrees, and an empty tree is 0. This 1 + max(left, right) shape recurs across tree problems — diameter, balance checking, and height-based DP all compute it as a side effect.

03

Approach

1

Define depth recursively

The depth of an empty tree is 0. The depth of any node is 1 + max(depth(left), depth(right)) — one for the node itself plus the deeper of its two subtrees. This is postorder in disguise: both children must answer before the parent can.

2

Answers bubble up from the leaves

Leaves compute 1 + max(0, 0) = 1; their parents combine those answers, and so on up to the root. No global state, no counters — each call returns a number and the recursion assembles them.

3

BFS alternative

Level-order traversal counts levels instead: pop a full level, increment depth, push the next. Same O(n), sometimes preferred when the tree is very deep (avoids recursion-stack limits) or when you need early exit for minimum depth.

04

Solution & live demo

▶1class Solution:
▶2    def maxDepth(self, root):
▶3        if not root:
▶4            return 0
▶5        left = self.maxDepth(root.left)
▶6        right = self.maxDepth(root.right)
▶7        return 1 + max(left, right)

05

Common pitfalls

Returning 1 for a null node

✗ Wrong

if not root:
    return 1

✓ Right

if not root:
    return 0

The empty tree has no levels. Returning 1 inflates every path by one and reports a depth one too large for every input, including single-node trees.

Adding instead of taking the max

✗ Wrong

return 1 + left + right

✓ Right

return 1 + max(left, right)

That counts total nodes on both sides rather than the longest single root-to-leaf path. Depth is about one path, not the whole subtree.

Tracking depth with a mutable global and forgetting to restore it

✗ Wrong

self.d += 1
dfs(node.left)
dfs(node.right)

✓ Right

return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

A shared counter incremented on the way down must be decremented on the way back up, or sibling subtrees inherit each other's depth. Returning the value makes the bookkeeping impossible to get wrong.

06

Edge cases

Empty tree

not root → return 0 immediately.

Skewed tree

One side is always empty (depth 0); the recursion effectively walks the chain, and depth equals node count.

Perfectly balanced tree

Both subtrees report equal depth; max just picks either and adds one.

07

Complexity

Time

O(n)

Space

O(h)

Every node answers once; recursion depth equals tree height (O(n) worst case, O(log n) balanced).