Approach Summary
Recursively: max(leftDepth, rightDepth) + 1. Null node returns 0.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Recursive Post-Order DFS (Optimal) | O(n) | O(h) call stack | Compute height recursively as 1 + max(left_depth, right_depth) with base case 0 for null. |
| 2 Approach 2: Iterative BFS Level Order Traversal | O(n) | O(w) where w is maximum tree width | Traverse level by level with a queue, incrementing depth on each finished level. |
Step 1: Baseline
Approach 1: Recursive Post-Order DFS (Optimal)
Time: O(n)
Space: O(h) call stack
A post-order traversal visits children before the parent. The maximum depth of any subtree rooted at node is 1 plus the larger of the depths of its left and right subtrees. The base case returns 0 when reaching a null pointer.
Approach 1: Recursive Post-Order DFS (Optimal) Implementation
Approach 1: Recursive Post-Order DFS (Optimal)
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
};class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
} Step 2: Most Optimized
Approach 2: Iterative BFS Level Order Traversal
Time: O(n)
Space: O(w) where w is maximum tree width
Push root into a FIFO queue. While the queue is non-empty, determine the current level size, pop all nodes belonging to this level, push their children, and increment the depth counter by 1.
Approach 2: Iterative BFS Level Order Traversal Implementation
Approach 2: Iterative BFS Level Order Traversal
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
int depth = 0;
while (!q.isEmpty()) {
depth++;
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
}
return depth;
}
}class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
depth++;
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return depth;
}
};from collections import deque
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
depth = 0
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depthfunction maxDepth(root) {
if (!root) return 0;
const q = [root];
let depth = 0;
while (q.length > 0) {
depth++;
const levelSize = q.length;
for (let i = 0; i < levelSize; i++) {
const node = q.shift();
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
}
return depth;
}Edge Cases to Watch
- Empty tree (root is null; returns 0)
- Single node (returns 1)
- Skewed tree (linked list structure of depth n)
- Complete binary tree
Algorithmic Pattern
View Pattern Guide →
Master the Trees / DFS Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trees / DFS pattern.
Framework: Trees / DFS • Interview Prep: Tested at FAANG •
Explore all Trees / DFS problems & invariants →
How to Recognize This Pattern
- Tree height/depth
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(h)
Tags
Tree DFS BFS
Frequently Asked Questions
What is the optimal time and space complexity for Maximum Depth of Binary Tree?
The optimal solution for Maximum Depth of Binary Tree achieves O(n) runtime complexity and requires O(h) auxiliary space. Time complexity is O(n) where n is the number of nodes in the tree because every node is visited exactly once. Space complexity is O(h) where h is the height of the tree (O(log n) for balanced trees, O(n) for skewed trees) corresponding to the recursive call stack.
How do I identify that Maximum Depth of Binary Tree requires the Trees / DFS pattern?
In technical interviews, look for key problem signals: Tree height/depth. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trees / DFS strategy.
What critical edge cases must be handled in Maximum Depth of Binary Tree?
Essential edge cases to verify include: Empty tree (root is null; returns 0); Single node (returns 1); Skewed tree (linked list structure of depth n); Complete binary tree. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Maximum Depth of Binary Tree?
Maximum Depth of Binary Tree is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, LinkedIn.