Skip to main content

13. Maximum Depth of Binary Tree

easyAsked at Databricks

Find the maximum depth of a binary tree. Databricks uses this to test the canonical 'return aggregated value upward' tree recursion that maps directly onto cost estimation in Catalyst.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Databricks loops.

  • Glassdoor (2025-12)— Databricks SDE-I phone screen — used to gate further tree questions.
  • Blind (2026-Q1)— Common warm-up before harder tree recursion problems.

Problem

Given the root of a binary tree, 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.

Constraints

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

Examples

Example 1

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

Example 2

Input
root = [1,null,2]
Output
2

Approaches

1. BFS with level counter

Level-order traverse; count levels.

Time
O(n)
Space
O(w) — width of widest level
function maxDepth(root) {
  if (!root) return 0;
  let q = [root], depth = 0;
  while (q.length) {
    const next = [];
    for (const n of q) { if (n.left) next.push(n.left); if (n.right) next.push(n.right); }
    q = next;
    depth++;
  }
  return depth;
}

Tradeoff: Works but uses more memory than DFS on skinny trees. Use when JVM stack is a concern.

2. DFS — depth = 1 + max(left, right)

Standard structural recursion. Null returns 0.

Time
O(n)
Space
O(h) recursion stack
function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Tradeoff: Cleanest. The recurrence is exactly the definition.

Databricks-specific tips

Databricks grades this on whether you reach the one-line DFS without hesitation, then can pivot to the iterative variant when prompted ('what if the tree is 10,000 deep on a JVM with a 1MB stack?'). The bonus signal is articulating that Catalyst's cost estimator uses exactly this aggregation pattern — bubble a numeric aggregate up the tree.

Common mistakes

  • Returning depth of edges instead of nodes — leaf is depth 1, not 0.
  • Using a global counter instead of returning the value from recursion.
  • Forgetting the empty-tree case — null root must return 0, not crash.

Follow-up questions

An interviewer at Databricks may pivot to one of these next:

  • Minimum Depth of Binary Tree (LC 111) — careful, the null-child case is different.
  • Diameter of Binary Tree (LC 543) — same recursion shape with a side-effect.
  • How would Catalyst use this to estimate plan cost?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why 1 + max, not max + 1?

Just style; same answer. But the +1 represents 'this node' and the max picks the deeper child — read it left-to-right.

Is BFS or DFS better here?

DFS is shorter and uses O(h) stack. BFS uses O(w) heap. For balanced trees DFS wins; for skinny tall trees BFS avoids stack overflow.

Practice these live with InterviewChamp.AI

Drill Maximum Depth of Binary Tree and other Databricks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →