Maximum Depth of Binary Tree (LC 104)

Pattern: Tree DFS (Recursion)
Difficulty: Easy
Key Concept: The depth of a node is 1 + max(depth of left subtree, depth of right subtree); the base case is an empty subtree (depth 0).

Problem Statement

Given the root of a binary tree, return its maximum depth — the number of nodes along the longest path from the root down to a leaf (a node with no children).

Input: root — reference to the root of a binary tree (may be null).
Output: An integer — maximum depth.

Example 1

Output: 3 (path 3 → 20 → 7 or 3 → 20 → 15).

Example 2: Empty tree (root == null) → 0.

1. Algorithm & Pseudocode

Brute force

For each node in the tree, compute the height of the subtree rooted at that node by traversing down to every descendant again.
Alternatively: repeatedly traverse from root without memoization — for skewed trees you revisit the same nodes many times in overlapping subproblems.
Take the maximum height seen over all nodes as the “depth from root” — this is redundant; a cleaner brute force is: at every node, recompute full left height and full right height without sharing results between calls (still correct but does duplicate work).

Pseudocode (naive / redundant DFS)

function heightFrom(node):
    if node is null: return 0
    leftH = heightFrom(node.left)   // full subtree walk each time
    rightH = heightFrom(node.right)
    return 1 + max(leftH, rightH)

// Worst-case skewed tree: each level triggers full depth walk → O(n^2)
function maxDepthBrute(root):
    return heightFrom(root)  // if implemented without sharing, overlapping work on some variants

A classic O(n²) skewed-tree brute is: maxDepth(n) = 1 + max(maxDepth(n.left), maxDepth(n.right)) where each call re-scans — actually standard recursion is O(n). So define brute as:

Brute: Use BFS level-by-level with a simple list per level built by scanning all nodes each time, or two nested loops that for each node count path length to a leaf by walking again → quadratic in worst case.

Practical brute (clear quadratic idea)

function depthToLeaf(node):
    if node is null: return 0
    if node.left == null && node.right == null: return 1
    return 1 + max(depthToLeaf(node.left), depthToLeaf(node.right))

function maxDepthSlow(root):
    // At each node in an inorder walk, call depthToLeaf — O(n) nodes × O(n) depth = O(n^2) skewed
    best = 0
    for each node x in inorder(root):
        best = max(best, depthFromRootToLeafThrough(root, x))  // custom path check
    return best

Simpler interview brute: iterative DFS with explicit stack storing (node, depth) — still O(n) one visit; pair it with “compare every root-to-leaf path length” by enumerating all paths stored in lists → O(n × h) time and O(n × h) space for storing paths.

Optimal

One post-order DFS: depth at node = 1 + max(depth(left), depth(right)).
Empty child contributes 0.
Single pass: each node visited once → O(n) time, O(h) recursion stack.

Pseudocode

function maxDepth(node):
    if node == null: return 0
    return 1 + max(maxDepth(node.left), maxDepth(node.right))

2. Step-by-Step Analysis (Beginner-Friendly)

Why recursion fits: Depth is defined recursively — the answer for the whole tree depends on answers for the left and right subtrees.
Why max(left, right): The longest root-to-leaf path goes through whichever side is deeper; we do not add both sides along one path.
Why null returns 0: Below a leaf there is no extra edge; we should not count “phantom” depth.
Brute path enumeration is slow because it materializes every path and uses extra memory; optimal DFS only keeps an integer per stack frame.

3. The Dry Run

Tree

Post-order evaluation (values are returned maxDepth for that subtree):

Step	Call	`node`	`left` result	`right` result	Return
1	`md(null)`	null	—	—	0
2	`md(9)`	9	0	0	1
3	`md(15)`	15	0	0	1
4	`md(7)`	7	0	0	1
5	`md(20)`	20	1	1	2
6	`md(3)`	3	1	2	3

ASCII (numbers under nodes = max depth of subtree rooted there)

        3  ← 3
       / \
      9   20  ← 1 and 2
     (1) /  \
        15   7  ← both 1
        (1) (1)

4. Java Solution

Brute Force

Enumerate all root-to-leaf paths; track maximum path length (number of nodes on path).

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class Solution {
    // Time: O(n * h) in worst case storing paths; skewed h = n → O(n^2)
    // Space: O(n * h) for all paths lists + recursion O(h)
    public int maxDepthBruteForce(TreeNode root) {
        if (root == null) return 0;
        List<List<Integer>> paths = new ArrayList<>();
        dfsPaths(root, new ArrayList<>(), paths);
        int best = 0;
        for (List<Integer> p : paths) best = Math.max(best, p.size());
        return best;
    }

    private void dfsPaths(TreeNode node, List<Integer> cur, List<List<Integer>> out) {
        cur.add(node.val);
        if (node.left == null && node.right == null) {
            out.add(new ArrayList<>(cur));
        } else {
            if (node.left != null) dfsPaths(node.left, cur, out);
            if (node.right != null) dfsPaths(node.right, cur, out);
        }
        cur.remove(cur.size() - 1);
    }
}

Optimal

class SolutionOptimal {
    // Time: O(n) — each node visited once
    // Space: O(h) — recursion stack; h = height, worst O(n) skewed
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return 1 + Math.max(left, right);
    }
}

Iterative BFS (also O(n) time, O(n) space at last level)

import java.util.ArrayDeque;
import java.util.Deque;

class SolutionBFS {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        int depth = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            depth++;
            for (int i = 0; i < sz; i++) {
                TreeNode n = q.poll();
                if (n.left != null) q.add(n.left);
                if (n.right != null) q.add(n.right);
            }
        }
        return depth;
    }
}

5. The “Java vs. Others” Edge

Prefer ArrayDeque<TreeNode> over LinkedList for BFS queues (fewer allocations, no Node wrapper per element).
Recursion depth on very deep skewed trees can overflow the JVM stack; in production you might use explicit stack iterative DFS.
Math.max is clear and idiomatic; no need for Integer.compare here.

6. Complexity Summary

Approach	Time	Space	Notes
Brute (all paths)	O(n × h) worst	O(n × h)	Stores every root-to-leaf path; skewed h = n
Optimal DFS	O(n)	O(h)	One visit per node; stack height = tree height
BFS level order	O(n)	O(w) w = max width	Queue holds up to one level; w ≤ n