Maximum Depth of Binary Tree

easy
TreesTreeBinary TreeDepth-First SearchBreadth-First Search

Given the root of a binary tree, return 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.

Examples

Example 1

  • Input: root = [3,9,20,null,null,15,7]
  • Output: 3
  • Explanation: The longest path is 3 -> 20 -> 15 (or 3 -> 20 -> 7), which has 3 nodes.

Example 2

  • Input: root = [1,null,2]
  • Output: 2

Constraints

  • The number of nodes in the tree is in the range [0, 10^4].
  • -100 <= Node.val <= 100

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursive DFS

Intuition

The simplest way to find the maximum depth is through recursion. At each node, the depth equals one plus the maximum depth of its left and right subtrees. The base case is a null node, which has depth zero. This naturally explores every path from root to leaf and returns the longest one. The recursion mirrors the tree structure itself, making it intuitive to reason about.

Algorithm

  1. If the root is null, return 0.
  2. Recursively compute the maximum depth of the left subtree.
  3. Recursively compute the maximum depth of the right subtree.
  4. Return 1 + max(leftDepth, rightDepth).
TimeO(n)SpaceO(h) where h is the height of the tree (O(n) in the worst case for a skewed tree)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};
Java 21
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}
Python 3.12
def maxDepth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))
Go 1.26
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    if left > right {
        return 1 + left
    }
    return 1 + right
}
Approach 2

Iterative BFS (Level Order)

Intuition

We can also find the maximum depth using breadth-first search. By processing the tree level by level, the number of levels we traverse equals the maximum depth. We use a queue to hold all nodes at the current level. For each level, we dequeue all current nodes and enqueue their children. Each complete level processed increments our depth counter.

Algorithm

  1. If the root is null, return 0.
  2. Initialize a queue with the root node and set depth to 0.
  3. While the queue is not empty, increment depth by 1.
  4. Process all nodes at the current level: for each node, add its non-null children to the queue.
  5. After the loop ends, return depth.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;
        while (!q.empty()) {
            int size = q.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return depth;
    }
};
Java 21
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 size = queue.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return depth;
    }
}
Python 3.12
from collections import deque


def maxDepth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth
Go 1.26
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{root}
    depth := 0
    for len(queue) > 0 {
        depth++
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return depth
}

Frequently asked questions

What is the optimal time complexity of Maximum Depth of Binary Tree?

The most efficient approach in this guide ("Iterative BFS (Level Order)") runs in O(n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Maximum Depth of Binary Tree use?

Maximum Depth of Binary Tree is a easy-level Trees problem involving Tree, Binary Tree, Depth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Maximum Depth of Binary Tree be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(h) where h is the height of the tree (O(n) in the worst case for a skewed tree), while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
root=
[]
Expected Output
0