Problem Statement #

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example #

Consider the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

The maximum depth is 3, as the longest path is: 3 → 20 → 15 (or 3 → 20 → 7).

Solution #

var maxDepth = function(root) {
    if (root === null) {
        return 0;
    }
    const left = root.left ? maxDepth(root.left) : 0;
    const right = root.right ? maxDepth(root.right) : 0;
    return 1 + Math.max(left, right);
};

Approach #

This is a classic binary tree recursion problem that demonstrates the power of recursive thinking. The key insight is that the maximum depth of a tree can be elegantly expressed in terms of its subtrees.

The recursive formula is:

• Maximum Depth = 1 + max(left subtree depth, right subtree depth)

This approach works because:

1. Every node contributes a depth of 1
2. The maximum depth through any node is determined by whichever subtree (left or right) goes deeper
3. We can apply this same logic recursively to each subtree until we reach the leaves

Why Recursion Works Here #

Binary trees have a naturally recursive structure—each node is itself the root of a smaller binary tree. This makes recursion an intuitive and elegant solution. By breaking the problem into smaller subproblems (finding the depth of left and right subtrees), we can solve the overall problem efficiently.

Code Explanation #

Let’s walk through the solution step by step:

Base Case: Handling Null Nodes #

if (root === null) {
    return 0;
}

The first thing we check is whether the current node is null. This is our terminating condition for the recursion. A null node isn’t a valid node in the tree and therefore contributes no depth. Returning 0 makes sense because there are zero nodes to count.

This base case is crucial—without it, our recursion would never terminate and would result in a stack overflow error.

Calculating Left Subtree Depth #

const left = root.left ? maxDepth(root.left) : 0;

Here we calculate the maximum depth of the left subtree. We use a ternary operator to check:

• If root.left exists (is not null), we recursively call maxDepth(root.left) to find its depth
• If root.left is null, we return 0 because there’s no subtree to explore

This recursive call will traverse down the entire left side of the tree, exploring all possible paths, until it hits null nodes.

Calculating Right Subtree Depth #

const right = root.right ? maxDepth(root.right) : 0;

This works identically to the left subtree calculation, but for the right side of the tree. By calculating both left and right depths, we ensure we explore all possible paths through the tree.

Combining Results #

return 1 + Math.max(left, right);

This is where the magic happens. We:

1. Take the maximum of the left and right subtree depths using Math.max(left, right)
2. Add 1 to account for the current node itself

The Math.max() function ensures we’re always counting the longest path, not just any path. This is essential because the problem asks for the maximum depth.

Time and Space Complexity #

Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once during the traversal.

Space Complexity: O(h), where h is the height of the tree. This represents the space used by the recursion call stack. In the worst case (a completely skewed tree), this could be O(n). In the best case (a balanced tree), this would be O(log n).

Alternative Approach: Iterative Solution #

While the recursive solution is elegant, we can also solve this problem iteratively using level-order traversal (BFS):

var maxDepth = function(root) {
    if (root === null) return 0;
    
    let depth = 0;
    let queue = [root];
    
    while (queue.length > 0) {
        let levelSize = queue.length;
        depth++;
        
        for (let i = 0; i < levelSize; i++) {
            let node = queue.shift();
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return depth;
};

This approach processes the tree level by level, incrementing the depth counter for each level.

Key Takeaways #

1. Recursion is natural for trees: The recursive structure of binary trees makes recursive solutions intuitive and clean
2. Base cases are essential: Always handle null nodes to prevent infinite recursion
3. Break down the problem: Complex tree problems can often be solved by breaking them into subtree problems
4. Multiple approaches exist: Both recursive (DFS) and iterative (BFS) solutions work, each with their own trade-offs

This problem is an excellent introduction to tree traversal and recursive thinking, forming the foundation for more complex tree algorithms.