Maximum Depth of Binary Tree

Easy Problem 63 of 151 Java and Python

Problem

Given the root of a binary tree, return its maximum depth: the number of nodes along the longest path from the root down to the farthest leaf.

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]
Output: 3
Why: 3 → 20 → 15 has three nodes.

Example 2

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

Constraints

0 ≤ number of nodes ≤ 10⁴

Explanation

A tree's depth is one more than the deeper of its two subtrees, and an empty tree has depth 0. That sentence is the whole recursive solution.

Alternatively, walk the tree level by level and count the levels.

Approach 1 · Better

Count levels with BFS

Time O(n)
Space O(w), w = widest level

Process the tree one level at a time with a queue; the number of levels is the depth.

Put the root in a queue (if any).
While the queue has nodes: remove the whole current level, add their children, and increment depth.

Java

import java.util.*;

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            depth++;
        }
        return depth;
    }
}

Python

from collections import deque

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue, depth = deque([root]), 0
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        return depth

Approach 2 · Optimal

Recursive DFS

Time O(n)
Space O(h)

Depth = 1 + max(depth of left, depth of right); null has depth 0.

If root is null, return 0.
Return 1 + max(maxDepth(left), maxDepth(right)).

Java

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

Python

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))

Complexity compared

Approach	Time	Space
Better Count levels with BFS	O(n)	O(w), w = widest level
Optimal Recursive DFS	O(n)	O(h)

Key takeaways

Most tree problems are "solve it for the children, then combine". Start by asking what each child should return.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem