Maximum Depth of Binary Tree
Last Updated: April 1, 2026
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. If the tree is empty (null root), the depth is 0. If the tree has just one node, the depth is 1.
The key observation is that the depth of a tree is recursive in nature. The depth of any node equals 1 (for itself) plus the maximum depth among its children. This naturally suggests a recursive approach. But we can also think about it level by level: how many levels does the tree have? That gives us a BFS-based approach.
Key Constraints:
Number of nodes in [0, 10^4]-- Up to 10,000 nodes. Any O(n) solution will work easily.Node values in [-100, 100]-- Node values don't matter for this problem. We only care about the tree's structure.0 nodesis valid -- We need to handle the empty tree (null root) case.
Approach 1: Recursive DFS
Intuition
This is one of those problems where the recursive solution is almost embarrassingly simple once you see it. The maximum depth of a binary tree rooted at some node is just 1 (counting the current node) plus the larger of the maximum depths of its left and right subtrees.
The base case is equally clean: if the node is null, the depth is 0. There is no node, so there is nothing to count.
That is the entire algorithm. The recursion handles everything. It dives down to the leaves, hits null, returns 0, and then each returning call adds 1 and picks the larger child. By the time we are back at the root, we have the answer.
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.
The recursive DFS is already O(n) in time, which is optimal. But the recursion stack uses O(h) space, and for deeply skewed trees that becomes O(n). What if we wanted to count levels directly instead of computing maximums bottom-up? BFS gives us exactly that.
Approach 2: Iterative BFS (Level Order Traversal)
Intuition
Here is another way to think about depth: it is just the number of levels in the tree. If we process the tree level by level using a queue, we can simply count how many levels we go through before running out of nodes.
BFS naturally works level by level. We start with the root in the queue. For each level, we process all the nodes currently in the queue (that is one full level), add their children, and increment our depth counter. When the queue is empty, we have visited every level and the counter holds the answer.
This approach is especially intuitive if you visualize the tree as horizontal layers. Level 1 is the root, level 2 is the root's children, level 3 is the grandchildren, and so on. The depth is just how many of these layers exist.
BFS processes nodes in order of their distance from the root. By counting how many times we fully drain a level from the queue, we are directly counting the number of levels. The last level we process corresponds to the deepest leaf, so the counter equals 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:
a. Record the number of nodes at the current level (the current queue size).
b. Process all nodes at this level: for each node, add its non-null children to the queue.
c. 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).