Maximum Depth of a Binary Tree (Count the Levels via BFS)

• BFS approach – run level-by-level traversal incrementing a counter per level; when the queue empties, the counter is the answer.
• DFS approach – recursively compute 1 + max(maxDepth(left), maxDepth(right)) with base case 0 for null.
• No early exit – unlike minimum depth, every node must be visited to find the farthest leaf.
• Time – O(n) for both approaches.
• Space – O(w) for BFS (widest level), O(h) for DFS (height/recursion stack).

What is the Maximum Depth problem?

The maximum depth of a binary tree is the number of nodes along the longest path from the root to the farthest leaf. If the root is null, the depth is 0. If the root has no children, the depth is 1.

Unlike minimum depth, there is no early exit here: every node must be visited to determine the farthest leaf.

How does the BFS approach work?

Run level-by-level BFS, incrementing a depth counter at the start of each non-empty level. When the queue drains completely, the counter holds the maximum depth.

package com.bank.service;

import java.util.*;

public class LongestApprovalChain {

    static class TreeNode {
        int value;
        TreeNode left, right;
        TreeNode(int val) { this.value = val; }
    }

    public static int maxDepthBFS(TreeNode root) {
        if (root == null) return 0;

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

        while (!queue.isEmpty()) {
            depth++;
            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);
            }
        }
        return depth;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.println("Maximum depth: " + maxDepthBFS(root));
    }
}

Maximum depth: 3

How does the DFS (recursive) approach work?

The one-line recursive solution computes 1 + max(maxDepth(left), maxDepth(right)) with base case 0 for a null node.

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

This visits every node once (O(n) time) and uses recursion stack proportional to the height (O(h) space).

How is maximum depth different from minimum depth?

| Aspect | Maximum Depth | Minimum Depth |
|---|---|---|
| Goal | Longest root-to-leaf path | Shortest root-to-leaf path |
| Early exit | No (must visit all nodes) | Yes (BFS stops at first leaf) |
| BFS advantage | No advantage over DFS | Strictly better |
| DFS pitfall | None | Single-child trap |
| Best algorithm | Either BFS or DFS | BFS preferred |

What is the space trade-off between BFS and DFS?

For maximum depth, both BFS and DFS visit all nodes and take O(n) time. The difference is space.

• DFS uses O(h) stack space where h is the height. For a balanced tree, h = log(n). For a degenerate (skewed) tree, h = n.
• BFS uses O(w) queue space where w is the maximum width. For a balanced tree, w = n/2 at the bottom level. For a degenerate tree, w = 1.

// Balanced tree: DFS uses O(log n) stack, BFS uses O(n/2) queue
// -> DFS is more memory-efficient for balanced trees

// Degenerate (skewed) tree: DFS uses O(n) stack, BFS uses O(1) queue
// -> BFS is more memory-efficient for degenerate trees

What are the edge cases?

• Null root – return 0.
• Single node – return 1.
• Left-skewed tree – depth equals n.
• Right-skewed tree – depth equals n.
• Perfect binary tree of height h – depth is h + 1 (counting nodes, not edges).

// Edge case: null root
System.out.println(maxDepthBFS(null)); // 0

// Edge case: single node
System.out.println(maxDepthBFS(new TreeNode(42))); // 1

What are common mistakes?

A common BFS mistake is forgetting to use the level-size snapshot, counting nodes instead of levels.

// WRONG: counting nodes
int depth = 0;
while (!queue.isEmpty()) {
    queue.poll();
    depth++; // counts nodes, not levels
}

// CORRECT: counting levels
while (!queue.isEmpty()) {
    depth++;
    int levelSize = queue.size();
    for (int i = 0; i < levelSize; i++) {
        queue.poll();
        // enqueue children
    }
}

A DFS mistake is returning -1 for null (counting edges) when the problem asks for nodes.

What is the time and space complexity?

Both BFS and DFS are O(n) time because every node is visited. BFS uses O(w) space; DFS uses O(h) space. Neither has an early exit for maximum depth.

What should a senior engineer know?

A senior engineer should articulate the space trade-off: for bushy trees, DFS is much lighter (O(log n) vs O(n/2)). For degenerate trees, BFS is lighter (O(1) vs O(n)). The choice depends on the expected tree shape and the risk of deep recursion. In production, if the tree might be very deep, the iterative DFS with an explicit stack avoids stack overflow.

They should also know that maximum depth equals the height of the tree when height is measured in nodes (some definitions measure in edges, giving height = depth - 1).