Maximum Depth of Binary Tree: Multiple Solutions and Complexity Analysis

Understanding Maximum Depth of a Binary Tree

The maximum depth (also called height) of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node. In other words, it measures how "tall" the tree is. A tree with only a root node has depth 1. An empty tree (null root) has depth 0 by convention, though some definitions treat it as -1 — we'll stick with 0 for clarity in our examples.

Why Maximum Depth Matters

Knowing the depth of a tree is fundamental to understanding its structure and performance characteristics. Here's why it matters:

• Balanced Tree Verification: A balanced binary tree has a depth of O(log n), while a degenerate (linked-list-like) tree has depth O(n). Computing depth is the first step in checking balance.
• Performance Implications: Many tree operations — search, insertion, deletion — have time complexity proportional to the tree's height. A shallow tree means fast operations.
• Algorithm Prerequisites: Problems like "diameter of binary tree," "minimum depth," and "lowest common ancestor" all build upon depth calculations.
• Serialization & Visualization: When printing a tree or serializing it to JSON, knowing the depth helps determine proper formatting and indentation.

Solution 1: Recursive DFS (Post-Order Traversal)

The most intuitive approach uses recursion. We traverse the tree in a post-order fashion: compute the depth of the left subtree, compute the depth of the right subtree, then return the larger of the two plus one for the current node. This mirrors the mathematical definition of height perfectly.

# Definition for a binary tree node.
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: TreeNode) -> int:
    """
    Calculate maximum depth using recursive DFS (post-order).
    Time Complexity:  O(n) — every node is visited exactly once.
    Space Complexity: O(h) — where h is the height of the tree (recursion stack).
                      In the worst case (degenerate tree), O(n).
                      In the best case (balanced tree), O(log n).
    """
    # Base case: an empty subtree contributes 0 depth
    if root is None:
        return 0
    
    # Recursively find the depth of left and right subtrees
    left_depth = max_depth_recursive(root.left)
    right_depth = max_depth_recursive(root.right)
    
    # The depth of the current node is 1 + the maximum of its children's depths
    return 1 + max(left_depth, right_depth)

# --- Example Usage ---
# Constructing:
#        1
#       / \
#      2   3
#     / \   \
#    4   5   6
#             \
#              7
if __name__ == "__main__":
    root = TreeNode(1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, None, TreeNode(6, None, TreeNode(7)))
    )
    print("Recursive DFS depth:", max_depth_recursive(root))  # Output: 4

How the Recursive Solution Works Step by Step

Let's trace the execution on a simple tree:

      1       max_depth(1) calls max_depth(2) and max_depth(3)
     / \      max_depth(2) calls max_depth(4) and max_depth(5)
    2   3     max_depth(4) returns 1 (no children)
             max_depth(5) returns 1
             max_depth(2) returns 1 + max(1, 1) = 2
             max_depth(3) calls max_depth(null) and max_depth(null)
             returns 1 + max(0, 0) = 1
             max_depth(1) returns 1 + max(2, 1) = 3

Each leaf returns 1, and the values bubble up, taking the maximum at each level. The recursion naturally handles the depth-first, bottom-up computation.

Complexity Analysis — Recursive DFS

• Time Complexity: O(n) where n is the number of nodes. We visit every node exactly once, performing constant-time operations at each (two recursive calls and a max comparison).
• Space Complexity: O(h) where h is the height of the tree. This space is consumed by the call stack. In a perfectly balanced tree, h = O(log n), which is excellent. However, in the worst case of a degenerate tree (essentially a linked list), h = n, giving O(n) space complexity. This can cause a stack overflow for very large skewed trees.

Solution 2: Iterative BFS (Level-Order Traversal)

A breadth-first approach uses a queue to traverse the tree level by level. The number of levels processed directly gives the maximum depth. This is elegant because it mirrors how we'd naturally count floors in a building — one floor at a time.

from collections import deque

def max_depth_bfs(root: TreeNode) -> int:
    """
    Calculate maximum depth using iterative BFS (level-order).
    Time Complexity:  O(n) — every node is visited exactly once.
    Space Complexity: O(n) in the worst case — the queue can hold up to
                      the maximum width of the tree (n/2 nodes at the
                      lowest level of a complete tree).
    """
    if root is None:
        return 0
    
    queue = deque([root])
    depth = 0
    
    while queue:
        # Process one entire level at a time
        level_size = len(queue)
        
        # Dequeue all nodes belonging to the current level
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # After finishing the level, increment depth
        depth += 1
    
    return depth

# --- Example Usage ---
if __name__ == "__main__":
    # Same tree as before
    root = TreeNode(1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, None, TreeNode(6, None, TreeNode(7)))
    )
    print("Iterative BFS depth:", max_depth_bfs(root))  # Output: 4

Level-by-Level Breakdown

The key insight is the level_size variable. At each iteration of the outer while loop, we snapshot the current queue length, which represents all nodes at the current depth. We then process exactly that many nodes, enqueuing their children (the next level) as we go. After the inner for-loop completes, we've finished one full level, so we increment depth.

Initial:  queue = [1]           depth = 0
Level 1:  level_size = 1, process [1], enqueue [2,3]  → depth = 1
Level 2:  level_size = 2, process [2,3], enqueue [4,5,6] → depth = 2
Level 3:  level_size = 3, process [4,5,6], enqueue [7] → depth = 3
Level 4:  level_size = 1, process [7], enqueue [] → depth = 4
Queue empty → exit, return 4

Complexity Analysis — Iterative BFS

• Time Complexity: O(n). Each node enters the queue exactly once and is dequeued exactly once. The inner loop performs constant work per node.
• Space Complexity: O(n) worst case, O(1) best case. In a complete tree, the queue holds up to n/2 nodes at the widest level. This is the trade-off compared to DFS — BFS uses more memory for wide trees but avoids recursion stack limits entirely.

Solution 3: Iterative DFS with Explicit Stack

We can simulate the recursive DFS using an explicit stack, where each stack entry stores a node along with its current depth. This eliminates recursion overhead and gives us control over the traversal order while maintaining O(h) space complexity like the recursive version — but without the risk of stack overflow from deep recursion.

def max_depth_iterative_dfs(root: TreeNode) -> int:
    """
    Calculate maximum depth using iterative DFS with an explicit stack.
    Time Complexity:  O(n) — every node is visited exactly once.
    Space Complexity: O(h) — stack holds at most h nodes at any time,
                      where h is the height of the tree.
                      Worst case (degenerate tree): O(n).
                      Best case (balanced tree): O(log n).
    """
    if root is None:
        return 0
    
    # Stack stores tuples of (node, depth_at_that_node)
    stack = [(root, 1)]
    max_depth = 0
    
    while stack:
        node, current_depth = stack.pop()
        
        # Update the maximum depth seen so far
        if current_depth > max_depth:
            max_depth = current_depth
        
        # Push children with depth = current_depth + 1
        # Note: pushing right first then left means we'll process left first
        # (LIFO), but order doesn't matter for computing max depth.
        if node.right:
            stack.append((node.right, current_depth + 1))
        if node.left:
            stack.append((node.left, current_depth + 1))
    
    return max_depth

# --- Example Usage ---
if __name__ == "__main__":
    root = TreeNode(1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, None, TreeNode(6, None, TreeNode(7)))
    )
    print("Iterative DFS depth:", max_depth_iterative_dfs(root))  # Output: 4

How the Stack-Based DFS Works

Instead of relying on the system call stack, we maintain our own stack data structure. Each time we pop a node, we check its depth against the running maximum and push its children with an incremented depth value. The stack naturally follows a depth-first traversal pattern. Since we track depth at each node explicitly, there's no need to reconstruct it from recursion returns.

Complexity Analysis — Iterative DFS

• Time Complexity: O(n). Every node is pushed onto the stack once and popped once. The operations at each step (comparison, appending children) are O(1).
• Space Complexity: O(h) where h is the height. The stack holds at most one path from root to a leaf at any given time. This matches the recursive DFS's space complexity but without the recursion overhead. In degenerate trees it's O(n); in balanced trees it's O(log n).

Comparing the Three Approaches

Here's a summary table to help you choose the right approach for your context:

Edge Cases and Common Pitfalls

• Empty Tree (root is None): All three solutions handle this gracefully by returning 0. Always include this check at the start of your function.
• Single Node Tree: Should return 1, not 0. Verify that your base case logic gives the correct answer — the recursive solution adds 1 to max(0, 0), yielding 1 correctly.
• Skewed Tree (Linked List): A tree where every node has only one child. Depth equals number of nodes. This is the worst-case space scenario for DFS approaches.
• Very Deep Trees: In languages like Python, the default recursion limit is around 1000. If your tree depth exceeds this, the recursive solution will crash with a RecursionError. Use an iterative approach for such cases.
• Modifying the Tree During Traversal: None of these solutions modify the tree structure. If your use case requires mutation, consider making a copy or using a read-only traversal.

Best Practices for Production Code

• Choose Based on Context: For most interview scenarios and production code with reasonably sized balanced trees, the recursive DFS is preferred for its clarity and conciseness. For unknown or potentially degenerate trees, prefer iterative DFS to avoid stack overflow.
• Use Type Hints: Always annotate function signatures with type hints (as shown in the examples) — this improves code readability and enables static analysis.
• Document Complexity: Include docstrings that specify time and space complexity. This helps teammates understand performance implications at a glance.
• Test Edge Cases: Write unit tests covering empty tree, single node, balanced tree, left-skewed, right-skewed, and complete tree scenarios.
• Consider Iterative DFS as Default: It offers the best of both worlds — O(h) space like recursion without the recursion limit risk. If code clarity is paramount, recursion is fine for controlled environments.

Practical Application: Checking Tree Balance

Once you can compute maximum depth, a natural extension is checking whether a tree is balanced. A balanced tree is one where, for every node, the depth difference between its left and right subtrees is at most 1. Here's how depth computation integrates into a balance check:

def is_balanced(root: TreeNode) -> bool:
    """
    Check if a binary tree is height-balanced.
    Uses a modified recursive DFS that returns -1 to signal imbalance,
    avoiding O(n²) repeated depth calculations.
    Time Complexity: O(n)
    Space Complexity: O(h)
    """
    def check_height(node: TreeNode) -> int:
        if node is None:
            return 0
        
        left_height = check_height(node.left)
        if left_height == -1:
            return -1  # Left subtree is unbalanced, propagate failure
        
        right_height = check_height(node.right)
        if right_height == -1:
            return -1  # Right subtree is unbalanced, propagate failure
        
        # Check balance condition at this node
        if abs(left_height - right_height) > 1:
            return -1  # Current node is unbalanced
        
        # Return the actual height of this subtree
        return 1 + max(left_height, right_height)
    
    return check_height(root) != -1

# --- Example Usage ---
if __name__ == "__main__":
    # Balanced tree
    balanced_root = TreeNode(1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, TreeNode(6), TreeNode(7))
    )
    print("Is balanced:", is_balanced(balanced_root))  # Output: True
    
    # Unbalanced tree (the one from earlier examples)
    unbalanced_root = TreeNode(1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, None, TreeNode(6, None, TreeNode(7)))
    )
    print("Is balanced:", is_balanced(unbalanced_root))  # Output: False

This example demonstrates how the depth calculation can be augmented to solve a more complex problem efficiently. Instead of naively computing depths independently for each node (which would be O(n²)), we compute heights bottom-up and short-circuit as soon as an imbalance is detected.

Language-Specific Considerations

Python

Python's recursion limit (sys.getrecursionlimit(), typically 1000) means you should prefer iterative solutions for trees deeper than ~900 nodes. You can increase the limit with sys.setrecursionlimit(), but that's a band-aid — iterative is safer.

JavaScript / TypeScript

JavaScript engines vary in their call stack size, but deep recursion can throw "Maximum call stack size exceeded" errors. Use an explicit stack or BFS for production code handling arbitrary trees.

// TypeScript: Iterative DFS with explicit stack
function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;
    
    const stack: [TreeNode, number][] = [[root, 1]];
    let maxDepth = 0;
    
    while (stack.length > 0) {
        const [node, depth] = stack.pop()!;
        maxDepth = Math.max(maxDepth, depth);
        
        if (node.right) stack.push([node.right, depth + 1]);
        if (node.left) stack.push([node.left, depth + 1]);
    }
    
    return maxDepth;
}

Java

Java's call stack is larger than Python's by default, but for extremely deep trees (e.g., 10,000+ nodes skewed), you'll still hit a StackOverflowError. Use ArrayDeque for BFS or an explicit Stack for DFS.

// Java: Iterative BFS approach
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    
    Queue 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;
}

Conclusion

Computing the maximum depth of a binary tree is a foundational algorithm that opens the door to understanding tree structures, analyzing performance, and solving more complex tree-based problems. We've explored three robust solutions — recursive DFS, iterative BFS, and iterative DFS — each with distinct trade-offs in space complexity and practical robustness. The recursive approach wins on elegance and is perfectly suited for balanced trees in controlled environments. BFS shines when you need level-order information alongside depth, or when dealing with very narrow but deep trees. Iterative DFS provides the safety of an explicit stack while maintaining the same asymptotic space complexity as recursion. By understanding all three, you equip yourself to handle any tree depth scenario that arises in interviews, production systems, or competitive programming. Remember to always test edge cases, document your complexity analysis, and select the approach that best fits the constraints of your specific problem and runtime environment.