Maximum Depth of Binary Tree

Difficulty: Easy Source: NeetCode

Problem

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.

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

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Binary Trees — Understanding tree height vs depth distinction
• Recursion — Building answers bottom-up from leaf to root
• BFS — Level-by-level traversal where counting levels gives depth

1. Recursive DFS

Intuition

The depth of any tree is 1 (for the root) plus the maximum depth of either subtree. The base case is when the node is null — that contributes 0. This naturally gives a bottom-up computation.

Algorithm

1. If the node is null, return 0
2. Recursively get the depth of the left subtree
3. Recursively get the depth of the right subtree
4. Return 1 + max(left_depth, right_depth)

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth_recursive(root):
    if not root:
        return 0
    left_depth = max_depth_recursive(root.left)
    right_depth = max_depth_recursive(root.right)
    return 1 + max(left_depth, right_depth)

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 9, 20, None, None, 15, 7])
print(max_depth_recursive(root1))  # 3

root2 = build_tree([1, None, 2])
print(max_depth_recursive(root2))  # 2

root3 = build_tree([])
print(max_depth_recursive(root3))  # 0

root4 = build_tree([1])
print(max_depth_recursive(root4))  # 1

Complexity

• Time: O(n) — every node is visited once
• Space: O(h) — recursion stack depth equals tree height

2. Iterative BFS (Level Counting)

Intuition

BFS processes nodes level by level. If we count how many levels we process before the queue is empty, that count is the maximum depth.

Algorithm

1. If root is null, return 0
2. Initialize a queue with root and a depth counter at 0
3. For each level:
   • Increment depth
   • Process all nodes at this level, enqueuing their children
4. Return depth when queue is empty

Solution

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth_bfs(root):
    if not root:
        return 0

    queue = deque([root])
    depth = 0

    while queue:
        depth += 1
        # Process all nodes at the current level
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return depth

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 9, 20, None, None, 15, 7])
print(max_depth_bfs(root1))  # 3

root2 = build_tree([1, None, 2])
print(max_depth_bfs(root2))  # 2

root3 = build_tree([])
print(max_depth_bfs(root3))  # 0

root4 = build_tree([1])
print(max_depth_bfs(root4))  # 1

Complexity

• Time: O(n) — every node is enqueued and dequeued once
• Space: O(w) — queue holds at most the widest level of the tree (up to n/2 nodes)

Common Pitfalls

Returning height instead of depth. In this problem, depth and height of the whole tree are the same thing, but make sure you understand: depth is measured from root down, height is measured from the node up to the deepest leaf.

Off-by-one with the BFS counter. Increment depth at the start of processing each level, not at the end. The for _ in range(len(queue)) pattern is key — it snapshots the current level size so you process exactly those nodes.