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.

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

python

▶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

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.

06

Complexity

Time

O(n)

Space

O(h)

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