Skip to main content

12. Maximum Depth of Binary Tree

easyAsked at ServiceNow

Find the maximum depth of a binary tree by counting the longest root-to-leaf path. ServiceNow uses this to probe tree-recursion fundamentals, reflecting their heavy use of hierarchical data models in CMDB and approval-chain trees.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Glassdoor (2025)— Appears in ServiceNow SDE-I phone screens as a warm-up tree problem.
  • LeetCode Discuss (2026)— Reported by candidates who completed ServiceNow early-career loops.

Problem

Given the root of a binary tree, return its maximum depth. The 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

Explanation: The deepest path is 3 -> 20 -> 15 (or 3 -> 20 -> 7), length 3.

Example 2

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

Approaches

1. Brute force iterative BFS

Level-order traversal, counting how many levels exist.

Time
O(n)
Space
O(n)
function maxDepth(root) {
  if (!root) return 0;
  let depth = 0;
  const queue = [root];
  while (queue.length) {
    depth++;
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return depth;
}

Tradeoff: Correct but uses O(n) queue memory; also queue.shift() is O(n) — use an index pointer or deque for production quality.

2. Recursive DFS

At each node, the depth equals 1 plus the maximum of its left and right subtree depths. Base case is null returns 0. Elegant and naturally expresses the sub-problem structure ServiceNow interviewers expect.

Time
O(n)
Space
O(h) where h = tree height
function maxDepth(root) {
  if (root === null) return 0;
  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);
  return 1 + Math.max(leftDepth, rightDepth);
}

Tradeoff: Clean and O(h) stack space. For a balanced tree h = log n; ServiceNow approval-chain hierarchies are typically shallow (<20 levels), so stack overflow is not a real concern.

ServiceNow-specific tips

ServiceNow interviewers care that you articulate the base case before writing code — null returns 0 is the entire insight, and candidates who jump to code before stating it often get confused. Bonus signal: mention that this pattern directly maps to computing the critical-path length in a ServiceNow workflow approval chain, where each node is an approval task.

Common mistakes

  • Forgetting the null base case, causing a TypeError on root.left when root is null.
  • Returning depth instead of 1 + depth, giving an off-by-one on every node.
  • Using BFS with queue.shift() in an interview setting — it's O(n) per shift; use an index or mention that a proper deque is needed.

Follow-up questions

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

  • Minimum depth (must reach a leaf, not just a node with one child).
  • Diameter of a binary tree (longest path between any two nodes).
  • Balance check: return -1 from recursion if subtrees differ by more than 1.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Is DFS or BFS preferred here?

Either gives O(n) time. DFS is terser and preferred in interviews. BFS is slightly more intuitive if you think of depth as 'number of levels', and it avoids recursion-stack overflow on degenerate trees.

What if the tree is a linked list (completely unbalanced)?

Recursion stack depth equals n, which can cause a stack overflow for n = 10^4 on some runtimes. Mention iterative DFS with an explicit stack as the production-safe version.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →