Maximum Depth of Binary Tree

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

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

The depth of a tree is one more than the depth of its deeper subtree.

The base case is an empty tree, whose depth is 0.

Alternatively, count how many levels a breadth-first traversal processes.

Common doubts

In nodes: an empty tree is 0, a single node is 1, and each level adds one.

The parent's depth depends on both children's depths, so you must resolve the children first — bottom-up.

For pathologically deep (skewed) trees where recursion could overflow the call stack.

Interview follow-ups

· What an interviewer asks next.

Take the min of the subtree depths, but be careful: a node with one missing child must use the present child's depth, not 0 (LeetCode 111).

Balance uses the same height computation but also compares the two subtree heights at every node.

Fun facts

Maximum depth equals the number of levels a breadth-first traversal produces.
This recurrence is the seed of many tree DPs: height, balance, diameter, and path sums all extend it.

Asked at

AmazonMicrosoftLinkedIn

Frequently Sometimes Occasionally

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]
Output: 3
The longest root-to-leaf path 3 -> 20 -> 15 (or 3 -> 20 -> 7) has 3 nodes.

Example 2

Input: root = [1, null, 2]
Output: 2
The path 1 -> 2 has 2 nodes.

Constraints

- The number of nodes is in the range [0, 10^4] - -100 <= Node.val <= 100

The maximum depth of a tree is one more than the deeper of its two subtrees' depths. That single sentence is the whole recursion: an empty tree has depth 0, and any node contributes 1 on top of max(left depth, right depth).

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary tree. Nodes with a value and up to two children (left, right).

Recursion / postorder. The node's answer depends on its children's answers, so compute children first.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Depth in nodes or edges?”

Here it's the number of nodes on the longest root-to-leaf path; an empty tree is 0, a single node is 1.

“Can the tree be empty?”

Yes — return 0.

The ideal opening — say it like this

The depth of a tree is one plus the maximum depth of its two subtrees, with an empty tree being zero.

That's a direct recursion; I could also count levels with a breadth-first traversal.

Understand the problem

Worked example — tree [3, 9, 20, null, null, 15, 7]

        3            depth(15)=1, depth(7)=1
       / \           depth(20)=1+max(1,1)=2
      9   20         depth(9)=1
         /  \        depth(3)=1+max(1,2)=3
        15   7
answer: 3

Key observations

1Aha

Depth = 1 + max of subtree depths

The recurrence is the entire solution; the base case (null → 0) makes it terminate.

2Aha

It's a postorder aggregation

You need both children's depths before you can answer for the parent — classic bottom-up recursion.

3Aha

BFS counts levels

The number of levels in a breadth-first traversal equals the maximum depth — a natural iterative alternative.

Brute force vs optimal

	BFS level count	Recursive depth
Idea	Count levels with a queue	1 + max(depth(left), depth(right))
Time	O(n)	O(n)
Space	O(n) queue	O(height) recursion

Both are O(n); the recursion is a one-liner, BFS avoids deep call stacks. Full code is in the Approaches selector below.

Summary

Key takeaway

Maximum depth = 1 + max(left depth, right depth), with an empty tree contributing 0. O(n) time, O(height) space recursively.

depth(node):
    if node is null: return 0
    return 1 + max(depth(node.left), depth(node.right))