LeetCode · #104

Maximum Depth of Binary Tree Solution

Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from root to the farthest leaf.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #104

🏗️

Pattern

Recursion — bottom-up depth

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

 Input: [3, 9, 20, null, null, 15, 7]
Output: 3 //     3        depth 1 //    / \ //   9   20     depth 2 //      /  \ //     15   7   depth 3 

Constraints

• 0 ≤ number of nodes ≤ 10⁴ • -100 ≤ Node.val ≤ 100

Section Two · Approach 1

BFS Level Count — O(n)

Use a queue for level-order traversal. Count the number of levels — that's the depth. Process all nodes at each level before moving to the next.

Section Three · Approach 2

Recursive DFS — O(n)

The depth of a tree = 1 + max(depth of left subtree, depth of right subtree). Base case: null node has depth 0. This is the canonical bottom-up tree recursion.

💡 Mental model: Ask each child "how deep are you?" Take the bigger answer, add 1 (for yourself). Leaves answer 1 (they have no children, so max(0,0)+1). The root's answer is the tree's depth.

🎯 Foundation pattern:

This "ask children, combine answers" pattern is the basis of most tree problems: max depth, min depth, diameter, balanced check, path sum.
Master this recurrence first.

Section Four · Trace

Visual Walkthrough

Bottom-up depth calculation

Section Five · Implementation

Code — Java & Python

Java — Recursive DFS

 class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

Python — Recursive DFS

 class Solution:
def maxDepth(self, root) -> int:
if not root: return 0 return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Recursive DFS	O(n)	O(h) — call stack
Iterative BFS	O(n)	O(n) — queue

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty	`null`	Depth = 0.
Single node	`[1]`	Depth = 1.
Skewed	`1→2→3→4`	Depth = n. Stack depth = n (worst case).

⚠ Common Mistake: Returning 1 for null nodes instead of 0. Null means "no node here" — depth 0. A leaf is depth 1 because it exists. Off-by-one errors cascade through the entire tree.

← Back to Trees problems

LearningTree

LC 104 · Maximum Depth of Binary Tree — Solution & Explanation | DSA Guide