Maximum Depth of Binary Tree - Solution & Explanation

Problem Overview: Given the root of a binary tree, return its maximum depth. The depth is the number of nodes along the longest path from the root down to a leaf node. You need to traverse the tree and determine how far the deepest branch extends.

Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))

This approach uses recursion to explore the tree using Depth-First Search. For each node, recursively compute the depth of its left and right subtrees. The maximum depth at that node is 1 + max(leftDepth, rightDepth). The recursion naturally mirrors the structure of the binary tree, making the implementation very concise. Time complexity is O(n) because every node is visited once. Space complexity is O(h), where h is the tree height, due to the recursion stack. In the worst case of a skewed tree, this becomes O(n); for balanced trees it is O(log n). This is the most common solution used in interviews.

Approach 2: Breadth-First Search (BFS) using Queue (Time: O(n), Space: O(w))

This method traverses the tree level by level using Breadth-First Search. Start by pushing the root node into a queue. For each level, process all nodes currently in the queue, then push their left and right children. After finishing a level, increment the depth counter. Continue until the queue becomes empty. Since each node is enqueued and dequeued exactly once, the time complexity remains O(n). Space complexity is O(w), where w is the maximum width of the tree (the largest number of nodes at any level). This approach is useful when you want explicit control over level traversal.

Recommended for interviews: Recursive DFS is typically the expected solution because it directly models the recursive structure of a tree and results in very clean code. BFS using a queue demonstrates understanding of level-order traversal and iterative tree processing. Showing both approaches signals strong familiarity with tree traversal patterns.