LeetCode #104. Maximum Depth of Binary Tree

Time Complexity: O(n)

The function visits every node in the tree exactly once, where n is the total number of nodes. Each visit performs constant-time operations (comparison and addition), so the overall time complexity is linear.

Space Complexity: O(h)

h = height of the tree (maximum depth)
Best case (balanced tree): O(log n)

A perfectly balanced tree has height ≈ log₂(n).
So the deepest recursion chain is log(n) → stack size O(log n).

Worst case (skewed tree): O(n)

If each node only has one child (linked-list shape):
height = n
→ recursion stack size = n
→ O(n).

Average case: O(log n)

Random/typical trees tend to be reasonably balanced, so expected height ≈ log n.

Classic recursive problem because the depth of a tree is naturally defined in terms of the depths of its subtrees.

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        return Math.max(leftDepth, rightDepth) + 1;
    }
}

We recursively calculate the maximum depth of the left subtree and the right subtree:

int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);

As long as a node has children, the recursive calls continue deeper into the tree, and the current function cannot execute its return statement yet because it is waiting for the recursive results.

Once we reach a leaf node, its .left and .right are null, so the recursive calls hit the base case:

if (root == null) return 0;

At this point, the recursion starts returning upward (unwinding the call stack), and each node can finally execute:

return Math.max(leftDepth, rightDepth) + 1;

So:
Recursion goes down until null, then the return statements execute while coming back up.