104. Maximum Depth of Binary Tree

Quick Identifier

• Topic: trees
• Pattern: Tree DFS
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Apple, Bloomberg
• Frequency: Very High
• LeetCode: 104

Quick Sights

• Time Complexity: O(n) from the optimal approach.
• Space Complexity: O(h) from the optimal approach.
• Core Mechanism: Given the root of a binary tree, return the number of nodes along the longest path from the root down to a leaf (depth as edge count is often “levels − 1”; here LeetCode uses node count depth = root-to-leaf nodes).

Concept Explanation

Given the root of a binary tree, return the number of nodes along the longest path from the root down to a leaf (depth as edge count is often “levels − 1”; here LeetCode uses node count depth = root-to-leaf nodes).

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• "Maximum depth" / "height" of the tree
• Longest path root to any leaf
• Often first introductory recursion on trees

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — O(n) time / O(n) space — collect all root-to-leaf paths and take max length (overkill).
• Better — O(n) time / O(n) space — BFS level counting (same asymptotic, queue memory).
• Optimal — O(n) time / O(h) stack — DFS: depth = 1 + max(depth(left), depth(right)).

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftDepth := maxDepth(root.Left)
	rightDepth := maxDepth(root.Right)
	if leftDepth > rightDepth {
		return 1 + leftDepth
	}
	return 1 + rightDepth
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function maxDepth(root) {
	if (root === null) {
		return 0;
	}
	return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Walkthrough

Tree: 3 / 9,20 / null,null,15,7

Invariant: subtree depth is correctly computed bottom-up; empty subtree contributes 0.

Edge Cases

• root == null → depth 0
• Single node → depth 1
• Skewed list → depth n

Pitfalls

• Off-by-one: returning depth without +1 for current level
• Confusing edge-based height with node-based depth (stay consistent with problem definition)

Similar Problems

• 226. Invert Binary Tree — same traversal shell, different combine step.
• 110. Balanced Binary Tree — uses subtree heights for balance, not just max.
• 543. Diameter of Binary Tree — depth used to update a global best path length.

Variants

• Minimum depth to leaf → different combine (careful: not just min of children if one side null).
• Binary tree max width by level → BFS with level sizes.

Mind-Map Tags

#trees #dfs #height #recursion #divide-and-conquer-on-tree