Skip to main content
CodePeetCodePeet
CodePeet 150

Maximum Depth of Binary Tree

EASYProblemSolveExternal Links

Description

You are given the root of a binary tree. Your task is to find its maximum depth.

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

A leaf is a node with no children. If the tree is empty (root is null), the maximum depth is 0.

For example, in a tree with root 3, left child 9, and right child 20 (which has children 15 and 7), the maximum depth is 3. The longest path goes from root 3 → right child 20 → either child 15 or 7. That path has 3 nodes, so the depth is 3.

Examples

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]

Output: 3

Explanation: The tree has three levels. The root 3 is at depth 1. Nodes 9 and 20 are at depth 2. Nodes 15 and 7 are at depth 3. The longest root-to-leaf path contains 3 nodes (e.g., 3 → 20 → 15), so the maximum depth is 3.

Example 2

Input: root = [1, null, 2]

Output: 2

Explanation: The root node 1 has no left child and a right child 2. Node 2 is a leaf. The only root-to-leaf path is 1 → 2, which has 2 nodes. So the maximum depth is 2.

Constraints

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

Editorial

Brute Force

Intuition

Our first instinct might be to use Breadth-First Search (BFS) to find the maximum depth. BFS naturally processes the tree level by level using a queue. If we count how many levels we process before the queue runs out, that count is the maximum depth.

Think of it like descending a staircase one floor at a time. You process everyone on the current floor, note who's on the floor below, move down, and repeat. When there's no floor below, the number of floors you visited is the depth.

This approach works perfectly — you iterate through each level, count levels, and stop when the queue is empty. However, it requires explicit queue management and iterative logic that, while not slow, is more mechanical than necessary for such a clean recursive problem.

Step-by-Step Explanation

Let's trace through with root = [3, 9, 20, null, null, 15, 7]:

Step 1: Initialize: enqueue root [3]. depth = 0.

Step 2: Level 0 — queue has 1 node. Process node 3: enqueue children 9 and 20. Increment depth to 1.

Step 3: Level 1 — queue has 2 nodes. Process node 9: no children. Process node 20: enqueue 15 and 7. Increment depth to 2.

Step 4: Level 2 — queue has 2 nodes. Process node 15: no children. Process node 7: no children. Increment depth to 3.

Step 5: Queue is empty. No more levels to process.

Result: Maximum depth = 3.

BFS Level Counting — Iterative Depth Measurement — Watch how BFS processes the tree level by level, incrementing a depth counter after each level is fully processed. When the queue empties, the counter holds the maximum depth.

Algorithm

  1. If root is null, return 0
  2. Initialize a queue with the root node and set depth = 0
  3. While the queue is not empty:
    a. Record level_size = queue size
    b. For i from 0 to level_size - 1:
    • Dequeue a node
    • If it has a left child, enqueue it
    • If it has a right child, enqueue it
      c. Increment depth by 1
  4. Return depth

Code

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        
        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;
        
        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            depth++;
        }
        
        return depth;
    }
};
from collections import deque

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        queue = deque([root])
        depth = 0
        
        while queue:
            level_size = len(queue)
            for _ in range(level_size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        
        return depth
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();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            depth++;
        }
        
        return depth;
    }
}

Complexity Analysis

Time Complexity: O(n)

Every node is enqueued and dequeued exactly once. Each operation is O(1). With n nodes total, the time is O(n).

Space Complexity: O(n)

The queue holds at most one level of nodes at a time. In the worst case (a complete binary tree), the widest level has approximately n/2 nodes, so the queue uses O(n) space. In a skewed tree, the queue holds at most 1 node, giving O(1) space. Overall worst case: O(n).

Why This Approach Is Not Efficient

The BFS approach works correctly and runs in O(n) time, but it is more complex than necessary for this problem:

Unnecessary machinery: We use a queue, manage level sizes, and iterate through each level — all to answer a simple question: "how deep is this tree?" The BFS approach is designed for problems where you need to process nodes level by level (like level order traversal), but here we only care about the depth, not the individual levels.

Space usage: The queue can hold up to O(n/2) nodes for a complete binary tree. While this is still O(n), a recursive approach can solve the problem with only O(h) stack space (where h is the height), which is O(log n) for balanced trees.

The key insight: Maximum depth has a beautiful recursive structure. The maximum depth of a tree rooted at node X is 1 + max(depth of left subtree, depth of right subtree). This leads to an elegant 3-line recursive solution using Depth-First Search.

Optimal Approach - Recursive DFS

Intuition

The maximum depth of a binary tree has a natural recursive definition:

  • If the tree is empty (node is null), its depth is 0.
  • Otherwise, its depth is 1 (for the current node) plus the maximum of the depths of its left and right subtrees.

This is the essence of Depth-First Search (DFS) applied to depth calculation. We dive all the way to the bottom of each branch, then build the answer from the bottom up.

Imagine you're measuring the height of a family tree. You ask each person: "How many generations are below you?" Each leaf says "just me — 1 generation." Each parent says "I'm 1 generation plus however many are below my tallest child." The root's answer is the total depth.

This recursive approach is not just correct — it is the most elegant and natural way to solve this problem. The code is minimal, the logic is clean, and the recursion directly mirrors the mathematical definition of tree depth.

Step-by-Step Explanation

Let's trace through with root = [3, 9, 20, null, null, 15, 7]:

Step 1: Call maxDepth(3). Node 3 is not null. Recurse into both subtrees.

Step 2: Left subtree: maxDepth(9). Node 9 is not null. Recurse into both subtrees.

Step 3: maxDepth(null) — left child of 9. Returns 0.

Step 4: maxDepth(null) — right child of 9. Returns 0.

Step 5: Back at node 9: depth = 1 + max(0, 0) = 1. Return 1.

Step 6: Right subtree of root: maxDepth(20). Node 20 is not null. Recurse.

Step 7: Left of 20: maxDepth(15). Node 15 has no children. maxDepth(null) returns 0 twice. depth of 15 = 1 + max(0, 0) = 1. Return 1.

Step 8: Right of 20: maxDepth(7). Same as 15. depth = 1. Return 1.

Step 9: Back at node 20: depth = 1 + max(1, 1) = 2. Return 2.

Step 10: Back at root 3: depth = 1 + max(1, 2) = 3. Return 3.

Result: Maximum depth = 3.

Recursive DFS — Bottom-Up Depth Calculation — Watch how recursion dives to the leaves and builds the depth answer from the bottom up. Each node computes 1 + max(left_depth, right_depth), and the root's answer is the final result.

Algorithm

  1. Base case: if node is null, return 0
  2. Recursively compute leftDepth = maxDepth(node.left)
  3. Recursively compute rightDepth = maxDepth(node.right)
  4. Return 1 + max(leftDepth, rightDepth)

Code

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit every node exactly once. At each node, we do O(1) work (a comparison and an addition). Total: O(n).

Space Complexity: O(h), where h is the height of the tree

The only extra space is the recursion call stack, which goes as deep as the tree height. For a balanced tree, h = O(log n), so space is O(log n). For a completely skewed tree (like a linked list), h = n, so space is O(n) in the worst case.

Compared to the BFS approach, this is more space-efficient for balanced trees. BFS uses O(n/2) = O(n) queue space for the widest level of a complete tree, while DFS uses only O(log n) stack space. For skewed trees, both use O(n), but DFS achieves this with zero explicit data structures — just the call stack.

This recursive DFS solution is the canonical approach for maximum depth: minimal code, direct recursive structure, and optimal space for balanced trees.