Maximum Depth of Binary Tree
Understanding the Problem
We need to find how tall a binary tree is. The depth of a tree is the number of nodes on the longest root-to-leaf path. An empty tree (null root) has depth 0, and a single-node tree has depth 1.
The depth has a recursive structure: the depth of any node equals 1 (for itself) plus the larger of the depths of its two subtrees. That gives a recursive solution. The same quantity can be read level by level, which gives a breadth-first solution.
Key Constraints:
Number of nodes in [0, 10^4]-- Up to 10,000 nodes, so any O(n) solution is fast enough. A skewed tree can be 10,000 levels deep, which is relevant for recursion-stack depth.0 nodesis valid -- The empty tree (null root) must return 0, which forces an explicit null check.
Approach 1: Recursive DFS
Intuition
The maximum depth of a binary tree rooted at a node is 1 (counting the node itself) plus the larger of the maximum depths of its left and right subtrees. The base case is a null node, which has depth 0 because there is nothing to count.
These two rules define the whole computation. Each call descends to its children, the leaves return 0 for their null children, and every returning call adds 1 and keeps the larger child depth. The value returned at the root is the maximum depth.
Algorithm
- If the current node is null, return 0.
- Recursively compute the maximum depth of the left subtree.
- Recursively compute the maximum depth of the right subtree.
- Return 1 + max(leftDepth, rightDepth).
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node in the tree exactly once. Each visit does O(1) work (a comparison and an addition).
- Space Complexity: O(h), where h is the height of the tree. The recursion stack can go as deep as the height. In the worst case (a completely skewed tree), h = n, making it O(n). For a balanced tree, h = log n.
Recursive DFS runs in O(n) time, which is optimal, but its recursion stack uses O(h) space, reaching O(n) on a skewed tree. The next approach computes the same answer by counting levels directly with a queue, trading the recursion stack for a queue whose size depends on the tree's width rather than its height.
Approach 2: Iterative BFS (Level Order Traversal)
Intuition
The maximum depth equals the number of levels in the tree. A breadth-first traversal visits the tree one level at a time, so counting how many levels it processes gives the answer.
The traversal starts with the root alone in the queue. For each level, it removes every node currently in the queue (one full level), enqueues their children, and increments a depth counter. When the queue empties, the counter holds the number of levels, which is the maximum depth.
Recording the queue size before processing a level is what keeps levels separate. At the top of each iteration, the queue contains exactly the nodes at one distance from the root, because the previous iteration enqueued only their children. Fixing levelSize to that count means the inner loop consumes that level and no more, even though it also adds the next level to the same queue. The number of outer iterations is therefore the number of levels, which is the maximum depth.
Algorithm
- If the root is null, return 0.
- Initialize a queue with the root and set depth to 0.
- While the queue is not empty:
- Record the number of nodes at the current level (the current queue size).
- Process all nodes at this level: for each node, add its non-null children to the queue.
- Increment depth by 1.
- Return depth.
Example Walkthrough
Code
- Time Complexity: O(n). Every node is enqueued and dequeued exactly once.
- Space Complexity: O(w), where w is the maximum width of the tree. The queue holds at most one full level of nodes at a time. For a balanced binary tree, the widest level has roughly n/2 nodes, so this is O(n) in the worst case. For a skewed tree, each level has 1 node, so the space is O(1).