Finding Maximum Depth of Binary Tree - DFS vs BFS Approaches

The Maximum Depth of Binary Tree problem is a classic tree traversal challenge that introduces fundamental concepts of tree algorithms. This problem is perfect for understanding the relationship between recursion and tree structures.

Problem Statement

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

Tree Node Definition

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

Solution Strategies

Approach 1: Recursive DFS (Most Intuitive)

The recursive approach leverages the natural structure of trees and the call stack for traversal.

public class Solution {
    public int maxDepth(TreeNode root) {
        // Base case: if node is null, depth is 0
        if (root == null) {
            return 0;
        }

        // Recursive case: 1 + max depth of subtrees
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        return 1 + Math.max(leftDepth, rightDepth);
    }
}

Time Complexity: O(n) - visit each node once Space Complexity: O(h) - recursion stack depth, where h is tree height

Approach 2: Iterative DFS using Stack

Convert the recursive solution to iterative using explicit stack management.

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> depthStack = new Stack<>();

        nodeStack.push(root);
        depthStack.push(1);

        int maxDepth = 0;

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int currentDepth = depthStack.pop();

            maxDepth = Math.max(maxDepth, currentDepth);

            if (node.left != null) {
                nodeStack.push(node.left);
                depthStack.push(currentDepth + 1);
            }

            if (node.right != null) {
                nodeStack.push(node.right);
                depthStack.push(currentDepth + 1);
            }
        }

        return maxDepth;
    }
}

Time Complexity: O(n) Space Complexity: O(n) - explicit stack storage

Approach 3: BFS Level-Order Traversal

Use breadth-first search to process the tree level by level.

public 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 levelSize = queue.size();
            depth++;

            // Process all nodes at current level
            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;
    }
}

Time Complexity: O(n) Space Complexity: O(w) - where w is maximum width of tree

Comparison of Approaches

Approach	Pros	Cons	Best Use Case
Recursive DFS	Clean, intuitive code	Stack overflow for very deep trees	General use, interviews
Iterative DFS	No recursion limits	More complex code	Very deep trees
BFS	Level-by-level processing	Higher memory for wide trees	When you need level information

Key Insights

1. Tree Recursion Pattern: The recursive solution follows the classic tree pattern: base case for null, recursive case combining subtree results
2. Space-Time Tradeoffs: Different approaches have different space complexity characteristics
3. Stack vs Queue: DFS uses stack (LIFO), BFS uses queue (FIFO)
4. Tree Shape Matters: The optimal approach can depend on tree characteristics (deep vs wide)

Related Problems

• Minimum Depth of Binary Tree
• Binary Tree Level Order Traversal
• Balanced Binary Tree
• Diameter of Binary Tree

Conclusion

The recursive DFS approach is typically preferred for its simplicity and readability. However, understanding all three approaches helps build a solid foundation for more complex tree algorithms. The choice between them often depends on specific constraints like tree depth limits or memory requirements.

This problem beautifully demonstrates how the same logical approach can be implemented using different traversal strategies, each with its own trade-offs.