How do you approach Maximum Depth of Binary Tree?

Think about how to reconstruct the tree from the level-order array.

What is the time complexity of Maximum Depth of Binary Tree?

Time complexity: O(n) - visit each node once. Space complexity: O(n) - queue storage.

What are common mistakes on Maximum Depth of Binary Tree?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Maximum Depth of Binary Tree

EasyData Structures

Description

Given the root of a binary tree represented as a level-order array (with null for missing nodes), return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, [3, 9, 20, null, null, 15, 7] represents:

The maximum depth is 3.

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]

Output: 3

Example 2

Input: root = [1, null, 2]

Output: 2

Example 3

Input: root = []

Output: 0

Constraints

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

Maximum Depth of Binary Tree: approach, complexity and pitfalls

An easy trees problem, graded against 7 test cases (4 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

If you are stuck

Show the 3-step hint ladder

Think about how to reconstruct the tree from the level-order array.
You can use BFS (level-order traversal) to count the number of levels.
Alternatively, build the tree recursively and find the depth using DFS.

The optimal approach

Show the approach: BFS Level Counting

Use BFS to traverse the tree level by level. Count the number of levels to get the maximum depth. Build the tree from the level-order array by using a queue - each node's children are at indices `2*i + 1` and `2*i + 2`.

Alternatively, compute depth directly from the array using recursive DFS with index tracking.

Time: O(n) - visit each node once
Space: O(n) - queue storage

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.