Maximum Depth of Binary Tree

EasyTrees · DFS (Recursion)🧩 Tree DFS LeetCode #104 ↗Updated Oct 30, 2026

Problem

Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path that starts at the root and ends at a leaf. An empty tree has depth 0.

Inputroot = [1,2,3,null,4,null,null,5]Output4

Inputroot = [8,null,9]Output2

Inputroot = []Output0

0 ≤ nodes ≤ 10⁴ · -100 ≤ Node.val ≤ 100

Try it yourself

Java

class Solution {
    public int maxDepth(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The depth of a tree is defined recursively: 0 for an empty tree, otherwise 1 + max(depth(left), depth(right)). Trust the recursion — the definition is the algorithm.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceBFS, Counting Levels

Time O(n)Space O(w)

Process the tree level by level with a queue, snapshotting queue.size() to finish one full level per round. The number of rounds is the number of levels, which equals the maximum depth.

Java

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    int depth = 0;
    while (!queue.isEmpty()) {
        int size = queue.size(); // nodes on this level
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        depth++;
    }
    return depth;
}

Already linear and recursion-free, but needs a queue holding a whole level (up to ~n/2 nodes).

OptimalRecursive DFS (Post-order)

Time O(n)Space O(h)

Ask each child for its depth, take the larger one and add one for the current node. Every node is visited once, and the only memory is the call stack, which is as deep as the tree height h.

Java

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

Three lines, linear time, O(h) space — the canonical answer.

Pro tip

For a skewed tree h = n; if recursion depth is a concern, mention the BFS version (or an explicit stack of (node, depth) pairs).

At a glance

Level	Approach	Time	Space
Brute Force	BFS, Counting Levels	`O(n)`	`O(w)`
Optimal	Recursive DFS (Post-order)	`O(n)`	`O(h)`

Common pitfalls

Returning 1 for an empty tree — the base case is null → 0.
Confusing depth in nodes (this problem) with height in edges (off by one).
In BFS, incrementing depth per node instead of once per level.

Interview tips

Write the recursive one-liner first, then state O(n) time and O(h) space.
Offer BFS as the iterative alternative and compare O(h) vs O(w) memory.
Note that many tree problems (diameter, balanced check) reuse this exact recursion.

Pattern

Tree DFS returning a value from children → whenever a node's answer is built from its subtrees' answers (height, size, sums).

My notes saved in this browser