Maximum Depth of Binary Tree

Problem Description

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.

Examples

Constraints

• The number of nodes in the tree is in the range [0, 10⁴].
• -100 ≤ Node.val ≤ 100

Finding the Tallest Branch Recursively

The depth of a tree starting at the root is determined by the depths of its left and right subtrees. The maximum depth at any node is 1 + max(depth(left), depth(right)).

This definition translates directly to recursive depth-first search. The base case is a null node, which has a depth of 0. For any other node, we compute the depths of its left and right children, take the maximum, and add one to include the current level.

Solution 1: Recursive (DFS)

Recursively calculate the maximum depth of both children subtrees.

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

        // calculate height of subtrees
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

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

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0  # base case

        # calculate height of subtrees
        left_depth = self.maxDepth(root.left)
        # calculate height of subtrees
        right_depth = self.maxDepth(root.right)

        return 1 + max(left_depth, right_depth)

#include <algorithm>

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0; // base case

        // calculate height of subtrees
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        return 1 + std::max(leftDepth, rightDepth);
    }
};

Complexity Analysis:

• Time Complexity: O(n) where n is the number of nodes. Every node is visited once.
• Space Complexity: O(h) where h is the tree height, corresponding to call stack allocation.

Where it breaks: On a completely unbalanced linear tree with 10⁴ nodes, recursion will reach a depth of 10⁴. This can cause a stack overflow in systems with restricted stack space.

Solution 2: Level-Order Traversal (BFS)

Use a queue to traverse the tree level by level, incrementing a depth counter for each completed level.

import java.util.LinkedList;
import java.util.Queue;

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

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            // drain all nodes of the current level
            for (int i = 0; i < levelSize; i++) {
                TreeNode curr = queue.poll();
                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
            depth++;
        }
        return depth;
    }
}

from collections import deque


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

        queue = deque([root])
        depth = 0

        while queue:
            level_size = len(queue)
            # drain all nodes of the current level
            for _ in range(level_size):
                curr = queue.popleft()
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
            depth += 1

        return depth

#include <queue>

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;

        std::queue<TreeNode*> q;
        q.push(root);
        int depth = 0;

        while (!q.empty()) {
            int levelSize = q.size();
            // drain all nodes of the current level
            for (int i = 0; i < levelSize; i++) {
                TreeNode* curr = q.front();
                q.pop();
                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
            depth++;
        }
        return depth;
    }
};

Complexity Analysis:

• Time Complexity: O(n). We visit each node once.
• Space Complexity: O(w) where w is the maximum tree width.

Where it breaks: Uses heap allocation instead of call stack frames. Extremely wide trees can require large queues, increasing peak memory usage.

Common Mistakes

• Adding one to depth at the base case instead of returning 0. If you return 1 for a null root, your results will be off-by-one.
• Not processing all nodes of a level before incrementing depth in BFS. If you increment depth on every single node pop, the counter will track total nodes instead of tree levels.
• Returning the sum of child depths instead of the maximum. The depth is determined by the longest path, not the total size of the subtrees.

Frequently Asked Questions

How does this differ from the Minimum Depth of a Binary Tree problem? Minimum Depth (LeetCode 111) requires the path to end on a leaf node (a node with no children). If a node has only one child, the minimum path must continue down that child, whereas maximum depth always takes the longer path regardless.

Can we solve this using an iterative DFS with a stack? Yes. You can push pairs of (node, current_depth) onto a stack and maintain a running maximum of the depth. This matches the recursive DFS logic but avoids using the call stack.

What does this problem test in interviews? It tests your comfort with standard tree traversals (DFS and BFS) and your understanding of recursion flow.

← All Problems