Skip to main content

10. Binary Tree Inorder Traversal

easyAsked at Datadog

Return the inorder traversal of a binary tree's node values. Datadog asks this to test whether you can convert recursion to an explicit stack — the iterative form is required for traversing on-disk tree-indexed metric blocks where the recursion depth would blow the stack.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog backend — used as the lead-in to BST validation.
  • LeetCode Discuss (2025-09)— Mentioned in Datadog tagged set.

Problem

Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder = left subtree, root, right subtree.

Constraints

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

Examples

Example 1

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

Example 2

Input
root = []
Output
[]

Example 3

Input
root = [1]
Output
[1]

Approaches

1. Recursive DFS

Classic three-line recursion: left, root, right.

Time
O(n)
Space
O(h) recursion stack
function inorderTraversal(root) {
  const out = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.left);
    out.push(node.val);
    dfs(node.right);
  }
  dfs(root);
  return out;
}

Tradeoff: Recursion is fine for small trees but blows the JS call stack at h > ~10k. Datadog wants the iterative version.

2. Iterative with explicit stack (optimal)

Walk down the left spine, pushing as you go. When you hit null, pop, emit, then move to that node's right child and repeat.

Time
O(n)
Space
O(h)
function inorderTraversal(root) {
  const out = [];
  const stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    out.push(curr.val);
    curr = curr.right;
  }
  return out;
}

Tradeoff: Same O(n) time; explicit stack means no recursion-depth limit. Required for streaming traversal of large on-disk trees.

Datadog-specific tips

Datadog interviewers will press you for the iterative form even if your recursive answer is correct. They'll then ask: 'Now turn this into an iterator — return one value at a time on demand.' Show that the iterative version is already 70% there; just save (stack, curr) as state between yield calls.

Common mistakes

  • Pushing both children before processing — that's preorder/postorder, not inorder.
  • Forgetting the outer while condition (curr || stack.length) — terminating too early when curr goes null mid-traversal.
  • Trying Morris traversal under time pressure without practice — easy to get the thread-and-unthread logic wrong.

Follow-up questions

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

  • Convert this into a BST iterator that yields next() in amortized O(1) (LC 173).
  • Preorder/Postorder traversal — same stack logic, different push order.
  • Morris traversal — O(1) extra space using right-pointer threading.

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 is the iterative form preferred at scale?

JS engines cap call stack at ~10k frames. Trees from on-disk metric indices can be deeper. Explicit stack uses heap memory, which is bounded only by RAM.

What about Morris traversal?

Morris uses O(1) extra space by temporarily threading right pointers. It's elegant but error-prone — most companies (including Datadog) accept the explicit stack as 'good enough.'

Practice these live with InterviewChamp.AI

Drill Binary Tree Inorder Traversal 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 →