Maximum Depth of Binary Tree

Problem in plain words

You get the root of a binary tree. Count how many nodes sit on the longest path that starts at the root and goes straight down to some leaf, and return that count. An empty tree has depth 0; a single node has depth 1.

For example, a root 8 with a left child 4 and a right child 12, where 12 has its own left child 10, has depth 3 because the path 8 → 12 → 10 touches three nodes.

Intuition

The depth of a tree is defined in terms of the depths of its two subtrees: whichever side is deeper decides the answer, and the root adds one more level on top. That is a textbook post-order pattern — solve the children first, then combine their answers at the parent. The empty tree is the natural base case and returns 0.

Approach

1. If the node is null, return 0 — there are no levels below a missing node.
2. Recursively compute the depth of the left subtree.
3. Recursively compute the depth of the right subtree.
4. Return 1 + max(left, right): the current node plus the deeper of its two sides.

Dry run

Tree: 8 → left 4, right 12; 12 → left 10. Calls finish bottom-up:

Java solution

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return 1 + Math.max(left, right);
    }
}

Python solution

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Complexity

Edge cases and common mistakes

• Empty tree — return 0, not 1. Handling null as the base case covers this for free.
• Counting edges instead of nodes — this problem counts nodes, so a single node has depth 1.
• Only checking one side — a tree can be deep on the left and shallow on the right; always take the max of both.
• Very skewed trees — recursion depth equals tree height. For extremely deep inputs, switch to an iterative BFS.