Maximum Depth of Binary Tree

The cleanest way to solve this problem is to stop counting depth globally. Ask each subtree for its answer, then let the parent combine those answers.

Read the question as a contract

You receive the root of a binary tree. Return the number of nodes on the longest path from the root to a leaf.

That counting convention controls the entire implementation:

• An empty tree has depth 0.
• A tree containing only the root has depth 1.
• The values stored in nodes do not affect the result.
• The tree may contain 0 nodes.

For example:

        1
       / \
      2   3
         /
        4

The longest root-to-leaf path is 1 → 3 → 4, which contains three nodes. The answer is therefore 3.

This is easy to state and easy to get subtly wrong. Some versions of tree height count edges instead of nodes. Here, we count nodes, so a non-empty node contributes 1.

Recognize the subtree-return pattern

The important question is:

What should maxDepth(node) return for the subtree rooted at node?

It should return the maximum number of nodes on a path from node down to a leaf.

Once that contract is clear, the recurrence follows directly:

$$\text{maxDepth(node)} = 1 + \max(\text{maxDepth(node.left)}, \text{maxDepth(node.right)})$$

The 1 counts the current node. The max chooses the deeper child subtree.

A missing child is also easy to define:

$$\text{maxDepth(None)} = 0$$

That base case is not a special patch. It is a complete answer: an empty subtree contains zero nodes.

This makes the problem a natural tree depth-first search problem. Each call moves down to its children, waits for both results, and then computes the answer for the current node. In traversal terminology, the reasoning is postorder: resolve the children first, then process the parent.

Subtree contract: every call returns the maximum depth of the subtree it receives. The parent does not inspect the entire tree again; it combines two completed child answers.

Why a global counter is the weaker model

A tempting approach is to carry a mutable depth counter while traversing:

1. Increase the counter when descending.
2. Update a global maximum.
3. Decrease the counter when returning.

That can work, but it creates path-state bookkeeping. Every increment needs a matching decrement, and every shared variable becomes another place for a bug.

The return-value model is cleaner:

• The recursive call carries the tree structure through the call stack.
• Each subtree returns one integer.
• The parent combines those integers.

The algorithm is easier to prove because the function’s input and output have a precise meaning.

From traversal to the minimal algorithm

A baseline traversal can explore every root-to-leaf path while carrying the current depth. An explicit stack might store pairs such as (node, depth), and the algorithm would update the largest depth seen.

That baseline still has to inspect every node. In a general binary tree, any node may be part of the deepest path, so there is no safe shortcut that skips arbitrary subtrees.

The recursive version keeps the same necessary work but removes the manual path bookkeeping. Its obligations are exact:

1. If the node is missing, return 0.
2. Compute the depth of the left subtree.
3. Compute the depth of the right subtree.
4. Keep the larger child depth.
5. Add 1 for the current node.

The key combine operation is max, not addition. A path travels through one child at a time. Adding both child depths would count two separate branches as though they were one path.

For example, if the left subtree has depth 4 and the right subtree has depth 2, the current subtree has depth 5, not 7.

Prove the recurrence and dry-run the state

We can prove the recursive function correct with one claim:

For every node, maxDepth(node) returns the number of nodes on the longest path from that node to a leaf.

Base case

If node is None, the subtree is empty. Returning 0 matches the definition.

Inductive step

Assume the function correctly computes the depth of the left and right subtrees.

• maxDepth(node.left) gives the longest path below the left child.
• maxDepth(node.right) gives the longest path below the right child.
• Taking the larger result selects the longer downward path.
• Adding 1 counts the current node.

Therefore, the result is correct for node. Since the root is also a node, the result returned for the root is the maximum depth of the whole tree.

Now trace the earlier example:

        1
       / \
      2   3
         /
        4

The calls reach the leaves before returning:

Subtree	Left depth	Right depth	Returned depth
2	0	0	1
4	0	0	1
3	1	0	2
1	1	2	3

At node 1, the algorithm does not count all descendants. It compares the best path through each child and keeps the larger one.

That distinction matters:

• Maximum depth follows one root-to-leaf path.
• Subtree size counts every node.
• Those problems use different combine operations.

Implement the recursive Python solution

class Solution:
    def maxDepth(self, root: TreeNode | None) -> int:
        if root is None:
            return 0

        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)

        return 1 + max(left_depth, right_depth)

Read the code as the recurrence:

• The None check implements the base case.
• left_depth and right_depth ask the child subtrees for their answers.
• max(...) selects the deeper branch.
• 1 + counts the current node.

The node value is never read because values such as -7, 0, or 42 do not affect the tree’s shape. Only the links between nodes determine the depth.

For an interview, I would write the contract before writing the method:

None      -> 0
node      -> 1 + max(left depth, right depth)

That small step prevents most implementation mistakes.

Implementation checklist

Before submitting, verify:

• The empty tree returns 0.
• A single node returns 1.
• Both children are evaluated.
• The result uses max, not sum.
• The current node is counted exactly once.
• The method returns the computed integer.

Memoization is unnecessary here. In a tree, each node has one parent, so the same subtree is not normally reached through multiple paths. There is no repeated subproblem to cache.

Complexity and recursion tradeoffs

Let n be the number of nodes and h be the tree height.

Time: O(n)

Every node is visited once. At each node, the algorithm performs constant work:

• two child calls,
• one comparison,
• one addition.

The total work is therefore linear in the number of nodes.

Auxiliary space: O(h)

The recursive calls form a stack whose maximum size is the tree height.

A roughly balanced tree has height O(log n), so the call stack is also O(log n) in that shape. A completely skewed tree can have height n, producing O(n) stack usage.

This is auxiliary space: it does not count the input tree itself.

An iterative depth-first version can replace Python’s call stack with an explicit stack containing (node, depth) pairs. That avoids concerns about very deep recursion, but its worst-case auxiliary space is still O(n). For this problem, recursive DFS is usually the clearest default when the recursion depth is safe.

The practical rule is simple: choose the recursive version for clarity, and recognize explicit-stack DFS as the fallback when a tree can be extremely deep.

Edge cases and interview failure modes

Empty tree

root = None

The first condition returns 0.

Single-node tree

    7

Both children are empty, so the node returns:

1 + max(0, 0) = 1

This confirms that the problem counts nodes, not edges.

Left- or right-skewed tree

    1
   /
  2
 /
3

Each node adds one to the only non-empty child path, so the answer is 3. The same reasoning works if every child is on the right.

Uneven branches

        1
       / \
      2   3
           \
            4
             \
              5

The left subtree has depth 1. The right subtree has depth 3, so the root returns 1 + max(1, 3) = 4.

Do not choose a branch based on how many total descendants it contains. Choose the branch with the longest single downward path.

Duplicate or negative values

Values do not matter. A tree with repeated values has the same depth as an otherwise identical tree with distinct values.

Common incorrect approaches

Counting edges instead of nodes: returning 0 for a leaf would use a different convention. Under this contract, a leaf returns 1.

Exploring only one child: a shallow left branch may hide a deeper right branch. Both child depths must be computed.

Adding child depths: that counts two branches together, but a path can only follow one branch at each split.

Using a shared counter without restoring state: if you carry the current path depth manually, every descent must be balanced by a return. The subtree-return contract avoids that fragile bookkeeping.

When a recursive tree answer depends on the children, make the child results explicit. Hidden path state is where plausible solutions start to leak.

The reusable recognition rule

When a tree problem asks for a property of a subtree, begin with one question:

What exact value should this subtree return to its parent?

Then determine how the parent combines the child results:

• max for the longer path,
• min for the shorter path,
• sum for an aggregate,
• equality checks for structural comparisons,
• or another operation dictated by the problem.

For maximum depth, the contract is compact:

empty subtree -> 0
current node  -> 1 + max(left result, right result)

That rule is both the algorithm and its proof. In an interview, write those two lines first. Then translate them into code, dry-run them on an uneven tree, and check the node-counting convention before you move on.