C# LeetCode 104: Maximum Depth of Binary Tree - (Easy)

Problem

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Approach

How the function works

The function MaxDepth is recursive, meaning it calls itself to break the problem into smaller subproblems.

Base Case

If the current node is null (we’ve gone past a leaf), the depth is 0.

if (root == null) return 0;

Recursive Step:

For any non-null node, the maximum depth is 1 (for the current node itself) + the larger of the max depths of the left and right subtrees

return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));

So, the recursion explores all paths to leaves, and on the way back up, it calculates the maximum path length.

How recursion builds the numbers

Let’s take a simple example:

    1
   / \
  2   3
 / \
4   5

MaxDepth(1) = 1 + max(MaxDepth(2), MaxDepth(3))
MaxDepth(2) = 1 + max(MaxDepth(4), MaxDepth(5))
MaxDepth(4)
= 1 + max(MaxDepth(null), MaxDepth(null))
= 1 + max(0, 0)
= 1
MaxDepth(5) → 1

So,
MaxDepth(2) = 1 + max(1, 1) = 2
MaxDepth(3) = 1 + max(0, 0) = 1

Finally,
MaxDepth(1) = 1 + max(2, 1) = 3

How the call stack works

Each recursive call is pushed onto the call stack until it reaches a null node (base case).

Then the stack unwinds, returning numbers back up:

Push calls:

MaxDepth(1)
  → MaxDepth(2)
     → MaxDepth(4)
        → MaxDepth(null) → 0
        → MaxDepth(null) → 0

Once both children of 4 are done, we compute 1 + max(0,0) = 1 and return to caller.

Unwinding:

As the calls return:
Node 4 returns 1
Node 5 returns 1
Node 2 calculates 1 + max(1,1) = 2
Node 3 calculates 1 + max(0,0) = 1
Root calculates 1 + max(2,1) = 3

The stack ensures that we finish a subtree first before moving back up.

Why the numbers increase?

Every time we return from a node (stack call), we add 1 to represent that node in the depth count.

So the depth “grows” as the recursion unwinds from the bottom of the tree upward.

Code

public int MaxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
}