Maximum Depth of Binary Tree
Asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber
Problem
Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Meta | Easy | View all Meta questions → |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Apple | Easy | View all Apple questions → |
| Netflix | Easy | View all Netflix questions → |
| Uber | Easy | View all Uber questions → |
How to Think About It
Recursive DFS: the depth of a node is 1 + the maximum depth of its children. Base case: null node has depth 0.
Why it works: you're computing depth bottom-up. A leaf returns 1. Its parent returns 1+1=2. The root gets the maximum path length.
BFS alternative: count the number of levels during level-order traversal. Each level adds 1 to the depth.
Visual walkthrough for tree: 3
/ \n 9 20
/ \n 15 7
maxDepth(3) = 1 + max(maxDepth(9), maxDepth(20))
maxDepth(9) = 1 + max(0, 0) = 1 (leaf)
maxDepth(20) = 1 + max(maxDepth(15), maxDepth(7))
maxDepth(15) = 1 (leaf), maxDepth(7) = 1 (leaf)
maxDepth(20) = 1 + max(1, 1) = 2
maxDepth(3) = 1 + max(1, 2) = 3
Edge cases: empty tree (depth 0), single node (depth 1), skewed tree (depth = number of nodes).
Optimal Approach
Recursive DFS:
Step 1: Base case — if root is null, return 0.
Step 2: Recurse — return 1 + max(maxDepth(left), maxDepth(right)).
The formula "1 + max(left, right)" works because:
- The current node adds 1 to the depth
- The deeper child determines the path length
- The shallower child is ignored for maximum depth
Time: O(n) — visit every node once. Space: O(h) — recursion stack where h is tree height.
What Trips People Up in Real Interviews
Overcomplicating this. The depth is simply 1 + max(depth(left), depth(right)). Don't overthink it.
Forgetting the base case: a null node has depth 0. Without this, you'll get infinite recursion.
Confusing "depth" with "height." They're the same for binary trees — the number of nodes on the longest path from root to leaf.
Not handling an empty tree. Return 0, not -1 or null.
Counting edges instead of nodes. Depth is the number of nodes on the longest root-to-leaf path, not the number of edges. A single-node tree has depth 1, not 0.
Solution Code
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))Frequently Asked Questions
What is the Maximum Depth of Binary Tree problem?
Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
How do you solve Maximum Depth of Binary Tree?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Depth of Binary Tree?
Maximum Depth of Binary Tree is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber. It is a easy difficulty problem.
What are common mistakes on Maximum Depth of Binary Tree?
- Overcomplicating this. The depth is simply 1 + max(depth(left), depth(right)). Don't overthink it.
- Forgetting the base case: a `null` node has depth 0. Without this, you'll get infinite recursion.
- Confusing "depth" with "height." They're the same for binary trees — the number of nodes on the longest path from root to leaf.
- Not handling an empty tree. Return 0, not -1 or `null`.
- Counting edges instead of nodes. Depth is the number of nodes on the longest root-to-leaf path, not the number of edges. A single-node tree has depth 1, not 0.