Log inSign up
easyleetcodeNot Started

Maximum Depth of Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

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 · Example 1: Standard Tree:

Input: root = [3, 9, 20, null, null, 15, 7]
Output: 3
Explanation: Longest root-to-leaf path is 3 -> 20 -> 15 (length 3).

Example 2 · Example 2: Skewed Tree:

Input: root = [1, null, 2]
Output: 2
Explanation: Path is 1 -> 2 (length 2).

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -100 <= Node.val <= 100

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the fundamental 1 + max(L, R) bottom-up recurrence.
  • Compare recursive DFS depth computation with iterative BFS level counting.
  • Handle null root edge cases cleanly.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Compute longest root-to-leaf path.
  • Height of binary tree.
  • Maximum tree depth.

Algorithmic Decision Tree:

  • If root == null -> return 0.
  • Return 1 + max(dfs(root.left), dfs(root.right)).

Connected Patterns:

Minimum Depth of Binary TreeDiameter of Binary TreeBalanced Binary Tree

1. All Root-to-Leaf Path Collection

Intuition

Find all root-to-leaf paths using backtracking, store their lengths in a list, and find the maximum length.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If root == null return 0.
  2. Step 2: Traverse all paths from root to leaves.
  3. Step 3: Track path lengths in an array.
  4. Step 4: Return maximum length found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void getPaths(TreeNode* node, int cur, int& maxD) {
10 if (!node) return;
11 if (!node->left && !node->right) {
12 maxD = max(maxD, cur + 1);
13 return;
14 }
15 getPaths(node->left, cur + 1, maxD);
16 getPaths(node->right, cur + 1, maxD);
17 }
18 int maxDepth(TreeNode* root) {
19 if (!root) return 0;
20 int maxD = 0;
21 getPaths(root, 0, maxD);
22 return maxD;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n) — Visits all nodes and stores path representations.
  • Space complexity: O(n) — O(n) memory to store path records.

2. Iterative BFS Level Counting

Intuition

Initialize queue with root and depth = 0. While queue is not empty, increment depth and drain all nodes at the current level.

When to apply: When avoiding recursive call stacks.

Algorithm

  1. Step 1: If root == null return 0.
  2. Step 2: Initialize queue q, push root, depth = 0.
  3. Step 3: While q is not empty:
  4. - depth++.
  5. - Drain all q.size() nodes, pushing their children.
  6. Step 4: Return depth.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int maxDepth(TreeNode* root) {
10 if (!root) return 0;
11 queue<TreeNode*> q;
12 q.push(root);
13 int depth = 0;
14 while (!q.empty()) {
15 int sz = q.size();
16 depth++;
17 for (int i = 0; i < sz; ++i) {
18 TreeNode* node = q.front();
19 q.pop();
20 if (node->left) q.push(node->left);
21 if (node->right) q.push(node->right);
22 }
23 }
24 return depth;
25 }
26};
27
28int main() {
29 // Sample driver execution
30 cout << "Execution completed successfully." << endl;
31 return 0;
32}
33

Time & Space Complexity

  • Time complexity: O(n) — Processes all nodes in O(n) time.
  • Space complexity: O(w) — Queue holds maximum width w of tree.

3. Recursive Postorder DFS (Bottom-Up)

Intuition

If root is null, return 0. Otherwise return 1 + max(maxDepth(root.left), maxDepth(root.right)).

When to apply: Standard optimal solution in all interviews.

Algorithm

  1. Step 1: If root == null, return 0.
  2. Step 2: leftDepth = maxDepth(root.left).
  3. Step 3: rightDepth = maxDepth(root.right).
  4. Step 4: Return 1 + max(leftDepth, rightDepth).

Depth Trace for root = [3, 9, 20, null, null, 15, 7]

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Leaves 15 and 7 have depth 1
Visual state
Values and pointers at this exact step
tree
Root
3
L
9
R
20 (d=2)

Node order shown; add connections to display explicit tree edges.

curr: 20
Check / comparison
depth(20) = 1 + max(1, 1) = 2
Decision / next transition
Right subtree of root has depth 2.
Why this step matters

Step 1: Leaves 15 and 7 have depth 1. Node 20 evaluates 1 + max(1, 1) = 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int maxDepth(TreeNode* root) {
10 if (!root) return 0;
11 return 1 + max(maxDepth(root->left), maxDepth(root->right));
12 }
13};
14
15int main() {
16 // Sample driver execution
17 cout << "Execution completed successfully." << endl;
18 return 0;
19}
20

Time & Space Complexity

  • Time complexity: O(n) — Visits every node once in O(n) time.
  • Space complexity: O(h) — Recursion depth is tree height O(h).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Path EnumerationO(n)O(n)Backtracking to all leaves.Tracking path depths manually.
2.BFS Level CountingO(n)O(w)Count BFS rounds.Queue width.
3.Recursive Postorder DFSOptimalO(n)O(h)1 + max(left, right).None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root = [] -> returns 0.
  • Single node: root = [1] -> returns 1.
  • Completely skewed tree: depth equals n.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the recurrence relation clearly: depth(node) = 1 + max(depth(left), depth(right)).
  2. Explain the space complexity: O(h) where h is tree height (O(log n) best, O(n) worst).
  3. Mention that BFS takes O(w) space where w is the maximum width of the tree.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the maximum depth of an empty binary tree (root == null)?

Back to DSA Sheet