#104 Maximum Depth of Binary Tree

Easysolve on LeetCode ↗

frequently reported atLinkedIn Microsoft Apple Bloomberg Uber Amazon

the problem

In plain words

Return the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0.

in root = [3,9,20,null,null,15,7]

out 3

3 → 20 → 15 has three nodes.

in root = [1,null,2]

out 2

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

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree DFS (bottom-up)Tree BFS (level order)

The depth of a tree is 1 (for the root) plus the deeper of its two subtrees' depths. That one sentence is the whole solution.

solutions

From brute force to optimal

Ask both children for their depth, return 1 + the larger.

null → 0.
left = maxDepth(left), right = maxDepth(right).
Return 1 + max(left, right).

timeO(n)

One call per node, O(1) work each.

spaceO(h)

Recursion stack: O(log n) balanced, O(n) skewed.

javajava.util.*

1class Solution {2    public int maxDepth(TreeNode root) {3        if (root == null) return 0;                // empty tree has depth 04        int left = maxDepth(root.left);            // ask the left subtree5        int right = maxDepth(root.right);          // ask the right subtree6        return 1 + Math.max(left, right);          // me + the deeper side7    }8}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int maxDepth(TreeNode root) {3        if (root == null) return 0;                // empty tree has depth 04        int left = maxDepth(root.left);            // ask the left subtree5        int right = maxDepth(root.right);          // ask the right subtree6        return 1 + Math.max(left, right);          // me + the deeper side7    }8}

Process the tree one level at a time; the number of rounds is the depth.

Offer the root.
Each round: depth++, poll exactly size nodes, offer their children.
Return depth when the queue is empty.

timeO(n)

Each node is offered and polled once.

spaceO(w)

The queue holds at most one level (up to ~n/2 nodes).

javajava.util.*

1class Solution {2    public int maxDepth(TreeNode root) {3        if (root == null) return 0;4        Deque<TreeNode> queue = new ArrayDeque<>();5        queue.offer(root);6        int depth = 0;7        while (!queue.isEmpty()) {8            depth++;                               // entering a new level9            for (int size = queue.size(); size > 0; size--) {10                TreeNode node = queue.poll();11                if (node.left != null) queue.offer(node.left);12                if (node.right != null) queue.offer(node.right);13            }14        }15        return depth;16    }17}

Simulate recursion with two stacks: nodes and their depths. Track the max depth seen.

Push (root, 1).
Pop, update best, push children with depth + 1.

timeO(n)

Each node pushed and popped once.

spaceO(h)

At most one waiting sibling per level plus the current node — and it lives on the heap, so no StackOverflowError.

javajava.util.*

1class Solution {2    public int maxDepth(TreeNode root) {3        if (root == null) return 0;4        Deque<TreeNode> nodes = new ArrayDeque<>();5        Deque<Integer> depths = new ArrayDeque<>();   // depth of the node at the same position6        nodes.push(root);7        depths.push(1);8        int best = 0;9        while (!nodes.isEmpty()) {10            TreeNode node = nodes.pop();11            int depth = depths.pop();12            best = Math.max(best, depth);13            if (node.left != null) { nodes.push(node.left); depths.push(depth + 1); }14            if (node.right != null) { nodes.push(node.right); depths.push(depth + 1); }15        }16        return best;17    }18}

in the room

How to say it in the interview

talk track

Clarify: depth counts nodes here, so a single node returns 1 and an empty tree 0.
Give the one-line recurrence, code it, state O(n) time and O(h) space with both cases of h.
Offer BFS as the iterative alternative if they worry about deep trees.

traps

Returning Math.max(left, right) without the 1 + — every answer becomes 0.

what they ask next

Follow-ups

Minimum Depth (LC 111)?

Careful: a node with one child is not a leaf. BFS is cleanest — return the depth of the first leaf you poll.

Maximum depth of an N-ary tree (LC 559)?

Same idea: 1 + max over all children.

before you submit

Edge cases to test

Empty tree → 0.
One node → 1 (LeetCode counts nodes, not edges).
A 2000-node chain → 2000, with 2000 nested calls — fine here, but mention the iterative version for 10⁵.

practise next