Maximum Depth of Binary Tree - Video Solutions

Problem Overview: You are given the root of a binary tree and need to return its maximum depth. The depth is the number of nodes along the longest path from the root node down to the farthest leaf node. A leaf node has no children. The task is essentially measuring how tall the tree is.

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

This approach uses recursion to explore the tree depth-first. For each node, compute the depth of its left subtree and right subtree, then return 1 + max(leftDepth, rightDepth). The recursion naturally follows the structure of the tree, making the implementation compact and easy to reason about. Every node is visited exactly once, so the time complexity is O(n), where n is the number of nodes. The space complexity is O(h) due to the recursion call stack, where h is the tree height (worst case O(n) for a skewed tree, O(log n) for a balanced tree). This solution relies on concepts from Depth-First Search and works naturally with recursive Binary Tree traversal.

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

The BFS approach processes the tree level by level using a queue. Start by pushing the root node into the queue. For each level, iterate through all nodes currently in the queue, enqueue their children, and then increment a depth counter after finishing that level. The number of levels processed equals the tree depth. This method also visits every node once, resulting in O(n) time complexity. The space complexity is O(n) in the worst case because the queue may store an entire level of the tree at once (for example, the last level of a complete tree). This approach is based on Breadth-First Search and is useful when problems require explicit level-order traversal.

Recommended for interviews: Recursive DFS is the solution most interviewers expect first. The logic mirrors the definition of tree depth and results in very clean code. BFS with a queue is equally valid and demonstrates understanding of level-order traversal. Showing DFS first proves you understand recursive tree problems; mentioning BFS afterward signals deeper familiarity with multiple Tree traversal strategies.