Maximum Depth of Binary Tree Solution

Finding the maximum depth of a binary tree is a fundamental tree traversal problem that tests understanding of recursive and iterative approaches. This solution covers both BFS and DFS implementations with detailed complexity analysis.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input tree be empty, or is it guaranteed to have at least one node?
2. What is the expected time complexity constraint? Can we achieve O(n) or is O(n log n) acceptable?
3. Are we allowed to modify the input tree structure during our solution?
4. What is the maximum number of nodes we might encounter in the tree?
5. Should we return the depth as an integer or handle potential overflow?

Restatement in my own words: Given a binary tree, I need to find the maximum depth (also called height) of the tree. The maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

Input, Output, and Constraints:

• Input: A binary tree represented by its root node, where each node has a value and optional left/right child pointers
• Output: An integer representing the maximum depth of the tree
• Constraints:
  • Tree can have 0 to 10^4 nodes (based on typical FAANG constraints)
  • Node values are within standard integer range
  • The tree structure is valid (no cycles, proper parent-child relationships)

Assumptions I'm making:

• The tree is a valid binary tree (each node has at most 2 children)
• We're counting nodes in the longest path, not edges (though some variations count edges)
• The input tree can be safely modified if needed for our approach

Data shape and hidden structure:

• The input is a hierarchical tree structure with branching factor at most 2
• This is fundamentally a recursive or iterative traversal problem where we must explore all paths to leaf nodes
• The structure suggests we can think of this as a divide-and-conquer problem where the maximum depth of the whole tree equals 1 + max(depth(left_subtree), depth(right_subtree))

The problem has a clear recursive structure and is a classic example of tree traversal problems that can be solved efficiently with either DFS or BFS approaches.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern here is Tree Traversal with Depth Tracking. This problem fits the pattern of tree depth/height calculation, which is a classic application of either:

• Depth-First Search (DFS) with recursion or stack
• Breadth-First Search (BFS) with queue

Wording that signals the pattern

The key phrases that signal this pattern:

• "Maximum Depth" - indicates we need to find the longest path from root to leaf
• "Binary Tree" - establishes the tree structure with at most 2 children per node
• "Depth" - directly maps to tree traversal problems where we track levels

Why this problem fits that pattern

This is a fundamental tree structure problem where:

1. We need to traverse all paths from root to leaves
2. We must track the depth/level of each node during traversal
3. We want to return the maximum depth encountered
4. The recursive structure naturally fits the binary tree's hierarchical nature

Core insight needed to solve it

The core insight is that maximum depth equals the maximum of left subtree depth and right subtree depth, plus 1 (for the current node). This creates a clean recursive structure where:

• Base case: null node has depth 0
• Recursive case: depth = 1 + max(leftDepth, rightDepth)

This pattern is fundamental to many tree problems and demonstrates the power of divide-and-conquer approach on hierarchical data structures.

3. Approach Evolution

My first instinct is to use a recursive depth-first search approach because this problem naturally decomposes into subproblems - the maximum depth of a tree is 1 + max(depth of left subtree, depth of right subtree). But that's O(n²) in worst case for a skewed tree because we're recalculating depths repeatedly. Let me think about how to optimize this.

I notice that if I maintain the invariant that I'm always computing the depth from the root down to each node, I can reduce it to O(n) by computing each node's depth only once. The key insight is that I don't need to recompute the entire tree structure - I can compute depth as I traverse once.

The core approach is to use a recursive DFS that returns the maximum depth from each node. At each node, I return 1 + max(depth of left child, depth of right child). This gives me O(n) time complexity where n is the number of nodes, and O(h) space for recursion stack where h is the height.

Let me trace through this approach:

1. Base case: null node has depth 0
2. Recursive case: return 1 + max(depth of left subtree, depth of right subtree)
3. The invariant maintained is that at each node, we return the maximum path length from that node to a leaf

This approach is optimal because:

• We visit each node exactly once
• Each computation takes constant time
• The recursion stack depth is at most the tree height

The key optimization here is recognizing that this is a classic divide-and-conquer problem where the solution for a node depends only on its children's solutions, so we can compute it in one pass rather than recomputing subproblems.

Alternative approaches like iterative BFS or level-order traversal would also work but require additional space for a queue, making them less elegant than the clean recursive solution that naturally expresses the problem's structure.

4. Data Structure Choice

For this problem, I'll use the standard TreeNode class structure that represents a binary tree node, along with a queue for level-order traversal.

Primary Data Structures Used

1. TreeNode class:

   • Contains val, left, and right fields
   • Represents the fundamental building block of our binary tree
   • No additional space complexity impact beyond input size

2. Queue<TreeNode> (LinkedList):

   • Used for breadth-first search traversal
   • Allows us to process nodes level by level
   • Space complexity: O(w) where w is maximum width of the tree
   • Time complexity for enqueue/dequeue: O(1)

Why Each Data Structure Is Needed

The TreeNode class is essential because it defines the structure of our input data - each node has a value and two children that form the tree hierarchy. This is the fundamental data structure we're operating on.

The Queue serves as our primary mechanism for level-order traversal. It allows us to process all nodes at the current depth before moving to the next level, which is exactly what we need to count the maximum depth. Without a queue, we'd have to implement complex recursive logic or track depths manually.

Space and Time Impact

• Space: O(w) where w is the maximum width of the tree (for queue storage)
• Time: O(n) for processing all nodes once, where n is the total number of nodes

Helper Structure

I'm using the standard Java LinkedList as a queue implementation, which is appropriate for this use case because:

• It provides O(1) add and remove operations
• It's well-optimized for the typical queue usage pattern in tree traversal
• It's part of the standard Java collections framework, making it familiar and reliable

This choice keeps our solution clean, readable, and efficient without introducing unnecessary complexity or custom data structures.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works.

Consider this binary tree:

    3
   / \
  9   20
     /  \
    15   7

Step 1: Start with root node 3, queue contains [3], depth = 1 Step 2: Process node 3, add its children to queue: [9, 20], depth = 1 Step 3: Process node 9, no children to add: [20], depth = 1
Step 4: Process node 20, add its children: [15, 7], depth = 2 Step 5: Process node 15, no children: [7], depth = 2 Step 6: Process node 7, no children: [], depth = 2

The algorithm correctly returns 2 as the maximum depth.

Key insights during execution:

• We process nodes level by level using BFS
• Each time we finish processing all nodes at the current level, we increment depth
• The queue maintains exactly the nodes at the current level being processed
• When queue becomes empty, we've processed all levels and can return the final depth

Edge case handling:

• Empty tree: queue starts empty, return 0 immediately
• Single node: queue has one element, depth becomes 1, queue becomes empty, return 1
• Complete binary tree: all levels processed systematically

The algorithm terminates correctly because BFS guarantees we process each level completely before moving to the next, and we only increment depth when we've finished processing all nodes at the current level.

6. Java Solution

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        // Base case: if node is null, depth is 0
        if (root == null) {
            return 0;
        }
        
        // Recursive case: compute max depth of left and right subtrees
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        
        // Return 1 + maximum of left and right depths
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

This recursive solution follows the classic divide-and-conquer approach for tree problems. At each node, we compute the maximum depth of its left and right subtrees, then add 1 to account for the current node. The base case handles null nodes by returning 0 depth, which correctly propagates up through the recursion stack.

7. Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the binary tree. In the optimal approach using BFS or DFS, we must visit each node exactly once to determine the maximum depth. Even in the brute force approach with recursion, we still process each node once, making it O(n) time complexity.

Space Complexity: O(h) where h is the height of the binary tree. This space is used for the recursion call stack in the DFS approach or the queue in the BFS approach.

• For a balanced binary tree, h = O(log n), so space complexity becomes O(log n)
• For a skewed binary tree (essentially a linked list), h = O(n), making space complexity O(n)

The space complexity is optimal for this problem since we must store information about the tree traversal path to compute the maximum depth. In the worst case (skewed tree), we'll have n recursive calls on the call stack, which is unavoidable for a depth-first approach.

The solution is optimal because:

1. We visit each node exactly once (O(n) time)
2. We use the minimum necessary space to track the traversal state (O(h) space)
3. No additional data structures or preprocessing are required
4. The solution scales linearly with input size in both time and space

This complexity analysis holds for both the BFS and DFS approaches, with the only difference being the constant factors in space usage (BFS uses O(w) where w is maximum width, while DFS uses O(h)).

8. Edge Cases & Pitfalls

Empty Tree

The most fundamental edge case is when the input tree is null. In this case, the maximum depth should be 0, not 1. A common mistake is to return 1 when root is null, which incorrectly treats an empty tree as having depth 1.

Single Node Tree

A tree with only the root node should return depth 1. This is a simple case but often overlooked in implementation, especially when using recursive approaches that don't properly handle base cases.

Skewed Trees

Trees that are completely skewed (all nodes in a single path) can cause stack overflow with recursive approaches if the tree is very deep. While this isn't a correctness issue, it's a practical concern for very large inputs.

Integer Overflow

When dealing with very large trees, the depth calculation should not overflow integer values. However, in typical constraints, this is not a major concern since the maximum depth for practical inputs is well within integer limits.

Incorrect Base Case Handling

In recursive solutions, if the base case isn't properly handled (e.g., checking for null children before recursing), it can lead to incorrect depth calculations or runtime exceptions.

Misunderstanding Depth Definition

Some candidates confuse maximum depth with the number of nodes in the longest path. The correct definition is that maximum depth is the number of nodes along the longest path from root to leaf, which means a single node has depth 1.

Implementation Pitfalls

• Off-by-one errors: Adding 1 in the wrong place during recursion
• Not checking for null children: This can cause NullPointerExceptions
• Using iterative approach without proper queue handling: For BFS solutions, ensuring proper level tracking is crucial

// Example of incorrect handling:
// if (root == null) return 0; // Correct
// if (root == null) return 1; // Incorrect - returns 1 for empty tree

Common Mistake in Iterative Solutions

When implementing BFS with a queue, some candidates forget to properly track levels or incorrectly increment the depth counter when processing nodes at different levels. The key is to process all nodes at the current level before incrementing depth, or properly track when we've completed processing a level.

9. Alternative Approaches

There are several alternative approaches to solving the maximum depth of binary tree problem, each with different trade-offs:

Breadth-First Search (BFS) with Queue: Instead of recursion, we can use iterative BFS with a queue to traverse level by level. At each level, we increment our depth counter. This approach uses O(w) space where w is the maximum width of the tree, and has the same time complexity O(n). The advantage is that it avoids potential stack overflow for very deep trees.

Iterative DFS with Stack: Similar to BFS, we can implement iterative DFS using a stack. We maintain a stack of nodes along with their current depths. This approach also has O(h) space complexity where h is the height of the tree, but can be more memory-efficient than recursion in some cases.

Morris Traversal: For a space-optimized solution, we could theoretically adapt Morris traversal to track depth, though this is significantly more complex and less readable than the standard recursive approach. This would reduce space complexity to O(1) but at the cost of increased code complexity and potentially worse performance due to repeated traversals.

Bottom-up Approach: Instead of computing depth from root down, we could compute the maximum depth from leaves up by recursively finding the max depth of left and right subtrees and adding 1. This is essentially the same as our solution but with a different perspective on the recursion.

The recursive approach chosen in our solution is preferred because it's clean, readable, and directly expresses the problem's recursive structure. The iterative alternatives are useful when avoiding recursion is necessary (e.g., very deep trees or environments with limited stack space), but they add unnecessary complexity for most practical scenarios.

10. Test Cases

// Test case 1: Empty tree
TreeNode root1 = null;
assertEquals(0, maxDepth(root1));

// Test case 2: Single node
TreeNode root2 = new TreeNode(1);
assertEquals(1, maxDepth(root2));

// Test case 3: Balanced binary tree
//       3
//      / \
//     9   20
//        /  \
//       15   7
TreeNode root3 = new TreeNode(3);
root3.left = new TreeNode(9);
root3.right = new TreeNode(20);
root3.right.left = new TreeNode(15);
root3.right.right = new TreeNode(7);
assertEquals(3, maxDepth(root3));

// Test case 4: Skewed tree (all nodes on left)
//   1
//    \
//     2
//      \
//       3
TreeNode root4 = new TreeNode(1);
root4.right = new TreeNode(2);
root4.right.right = new TreeNode(3);
assertEquals(3, maxDepth(root4));

// Test case 5: Complete binary tree
//       1
//      / \
//     2   3
//    / \ / \
//   4  5 6  7
TreeNode root5 = new TreeNode(1);
root5.left = new TreeNode(2);
root5.right = new TreeNode(3);
root5.left.left = new TreeNode(4);
root5.left.right = new TreeNode(5);
root5.right.left = new TreeNode(6);
root5.right.right = new TreeNode(7);
assertEquals(3, maxDepth(root5));

The test cases cover:

• Empty tree: Validates base case handling
• Single node: Tests minimal valid input
• Balanced tree: Validates proper depth calculation with symmetric structure
• Skewed tree: Tests worst-case linear depth scenario
• Complete binary tree: Validates full tree traversal and maximum depth computation

Each test case uses a clear tree structure that makes the expected depth obvious, allowing for easy verification of the algorithm's correctness. The cases progress from simple to more complex structures to ensure comprehensive coverage of different tree topologies and edge conditions.

11. Final Summary

The core idea is to perform a depth-first traversal of the binary tree while tracking the maximum depth encountered, which can be efficiently solved using either recursive DFS or iterative BFS with a stack. This solution works because it systematically explores all paths from root to leaves, maintaining the maximum depth seen so far. The recursive approach is clean and intuitive, while the iterative approach avoids potential stack overflow for very deep trees. Both solutions are optimal with O(n) time complexity and O(h) space complexity, where h is the height of the tree, making them efficient for the given constraints.