Skip to main content

15. Minimum Depth of Binary Tree

easyAsked at Datadog

Return the minimum depth — the shortest path from root to a leaf. Datadog uses this as a BFS-vs-DFS tradeoff question: DFS visits every node, BFS short-circuits at the first leaf.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite tree warmup.
  • LeetCode Discuss (2025-08)— Datadog tagged set.

Problem

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf is a node with no children.

Constraints

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

Examples

Example 1

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

Example 2

Input
root = [2,null,3,null,4,null,5,null,6]
Output
5

Explanation: Right-only spine — only leaf is at depth 5.

Approaches

1. Recursive DFS

If a child is null, you can't take the 0-side — recurse on the other.

Time
O(n)
Space
O(h)
function minDepth(root) {
  if (!root) return 0;
  if (!root.left) return 1 + minDepth(root.right);
  if (!root.right) return 1 + minDepth(root.left);
  return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

Tradeoff: Visits every node. Correct, but doesn't short-circuit on a sparse tree.

2. BFS first-leaf (optimal)

Level-order traversal. The first leaf encountered IS at the minimum depth.

Time
O(n)
Space
O(w)
function minDepth(root) {
  if (!root) return 0;
  let q = [root];
  let depth = 1;
  while (q.length) {
    const next = [];
    for (const n of q) {
      if (!n.left && !n.right) return depth;
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    depth++;
    q = next;
  }
}

Tradeoff: Short-circuits at the first leaf. Beats DFS on unbalanced trees because BFS doesn't explore deep branches.

Datadog-specific tips

Datadog interviewers will probe: 'Why BFS here but DFS for max depth?' The correct framing — 'BFS finds the SHORTEST path first, so first leaf == answer' — earns points. DFS for max depth has no such short-circuit.

Common mistakes

  • Forgetting the 'a child is null' branch — returns 1 for a node like {val:1, left: null, right: {val:2}} when the answer is 2.
  • Using Math.min on two recursive calls without the null check — picks 0 from a null subtree.
  • Treating min as the recursion symmetric of max — they're NOT symmetric because leaves are nodes with both children null.

Follow-up questions

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

  • Max Depth (LC 104) — symmetric but easier.
  • Find leaves in level order — variant.
  • Datadog: 'Find the depth of the first error node in an aggregation tree.' Same algorithm.

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 doesn't Math.min(left, right) work directly?

Because a null child returns 0, and you'd take 0 + 1 = 1 even if the other child has a long path. A null child isn't a leaf — the parent itself isn't a leaf yet.

When does DFS beat BFS?

When the tree is balanced. BFS's queue width grows to n/2 at the bottom level. On balanced trees, recursive DFS has O(log n) stack.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →