Maximum Depth of Binary Tree - Solution & Explanation
Problem Statement
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 3
Example 2:
Input: root = [1,null,2] Output: 2
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. -100 <= Node.val <= 100
Approach Overview
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.
Approach 1: Recursive Depth-First Search (DFS)
This approach involves using a recursive function that traverses the tree in a depth-first manner. For each node, calculate the maximum depth of its left and right subtrees, and add 1 for the current node itself. The function returns the maximum of these two values. This provides an elegant and intuitive solution, leveraging the inherent recursive structure of trees.
The function maxDepth checks if the current node is null. If so, it returns 0, indicating no depth. Otherwise, it recursively computes the depth of the left and right subtrees, takes their maximum, and adds 1 to include the current node.
Complexity
Time Complexity: O(n) where n is the number of nodes, as each node is visited once.
Space Complexity: O(h) where h is the height of the tree, due to the stack space in recursion.
Approach 2: Breadth-First Search (BFS) using Queue
This approach involves using a queue to perform a Breadth-First Search (BFS) on the tree. By iterating level by level, we increment the depth counter with each level traversed completely.
The implementation expands upon queue operations for nodes. A queue holds nodes level-wise. Traverse nodes, extract them, and access their children for the new level until the queue is empty. Increment the depth after processing each level.
Complexity
Time Complexity: O(n) due to each node being visited once.
Space Complexity: O(n) where n is the maximum number of nodes at any level.
Approach 3: Recursion
Recursively traverse the left and right subtrees, calculate the maximum depth of the left and right subtrees, and then take the maximum value plus 1.
The time complexity is O(n), where n is the number of nodes in the binary tree. Each node is traversed only once in the recursion.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(n) where n is the number of nodes, as each node is visited once. |
| Breadth-First Search (BFS) using Queue | Time Complexity: O(n) due to each node being visited once. |
| Recursion | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Best general solution. Clean recursive logic that mirrors tree structure. Preferred in interviews. |
| Breadth-First Search (BFS) with Queue | O(n) | O(w) | Useful when performing level-order traversal or when recursion depth could be large. |
Video Solution
Maximum Depth of Binary Tree - 3 Solutions - Leetcode 104 - Python • NeetCode • 378,388 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Depth of Binary Tree easy or hard?
Maximum Depth of Binary Tree Python Java solution
How to solve Maximum Depth of Binary Tree in O(n)?
What is the best approach for Maximum Depth of Binary Tree?
Is Maximum Depth of Binary Tree asked at Google Amazon Meta?
What data structure is used in Maximum Depth of Binary Tree?
What is the time complexity of Maximum Depth of Binary Tree?
Ready to solve this problem?
Practice Maximum Depth of Binary Tree with our built-in code editor and test cases.
Practice on FleetCode