Maximum Depth of Binary Tree — Problem & Solution
Maximum Depth of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Depth of Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google, Microsoft and LinkedIn interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to the farthest leaf. An empty tree has depth 0.
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: 3
Explanation: The longest root-to-leaf paths are 3 → 20 → 15 and 3 → 20 → 7, each with three nodes.
Example 2
Input: root = [1,null,2]
Output: 2
Example 3
Input: root = []
Output: 0
Constraints
The number of nodes in the tree is in the range [0, 10^4]-100 <= Node.val <= 100
Hints for Maximum Depth of Binary Tree
Hint 1
The depth of a tree is one more than the depth of its deeper subtree.
Hint 2
That gives a two-line recursion whose base case is the empty tree, with depth 0.
Hint 3
Without recursion: a breadth-first search counts how many levels it processes.
How to solve Maximum Depth of Binary Tree
Depth satisfies depth(node) = 1 + max(depth(node.left), depth(node.right)) with depth(null) = 0, so one post-order recursion computes it.
Approach
- If
rootis null, return 0. - Compute the depths of the left and right subtrees recursively.
- Return
1 + max(left, right).
Why it works
Any root-to-leaf path leaves the root through exactly one child, so the longest one is the root plus the longest path in whichever subtree is deeper — exactly what the recurrence takes.
Complexity
- Time —
O(n) - Space —
O(h) recursion depth; a level-by-level BFS uses O(width) instead
Pitfalls
- Depth counts nodes, not edges: a single node has depth 1.
- An empty tree has depth 0.
Reference solution
Python
from typing import Optional
def maxDepth(root: Optional[TreeNode]) -> int:
if root is None:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))Java
public static int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}C++
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}JavaScript
var maxDepth = function(root) {
if (root === null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)