Skip to main content

64. Construct Binary Tree from Preorder and Inorder Traversal

mediumAsked at Datadog

Reconstruct a binary tree given its preorder and inorder traversals. Datadog uses this to test the divide-and-conquer recursion pattern with O(1) lookups via a position index — same shape as deserialization in their distributed metric storage layer.

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 — graded on O(1) inorder lookup.

Problem

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Constraints

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values.

Examples

Example 1

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

Example 2

Input
preorder = [-1], inorder = [-1]
Output
[-1]

Approaches

1. Recurse with array slicing

preorder[0] is root. Find it in inorder via indexOf. Slice and recurse.

Time
O(n^2)
Space
O(n^2)
function buildTree(preorder, inorder) {
  if (preorder.length === 0) return null;
  const root = { val: preorder[0], left: null, right: null };
  const i = inorder.indexOf(preorder[0]);
  root.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i));
  root.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1));
  return root;
}

Tradeoff: indexOf is O(n) per call; slice allocates. Quadratic overall. Datadog will push for O(n).

2. Index map + bounds (optimal)

Pre-index inorder values to positions in a Map. Recurse with [lo, hi] bounds on inorder; pre-iterator advances through preorder.

Time
O(n)
Space
O(n)
function buildTree(preorder, inorder) {
  const idx = new Map();
  inorder.forEach((v, i) => idx.set(v, i));
  let p = 0;
  function build(lo, hi) {
    if (lo > hi) return null;
    const val = preorder[p++];
    const node = { val, left: null, right: null };
    const mid = idx.get(val);
    node.left = build(lo, mid - 1);
    node.right = build(mid + 1, hi);
    return node;
  }
  return build(0, inorder.length - 1);
}

Tradeoff: O(n). Datadog-canonical: pre-index for O(1) lookup + bounds-only recursion (no slicing). Direct analog to their distributed deserializer.

Datadog-specific tips

Datadog grades on whether you reach for the inorder index map. Slicing and indexOf are the obvious wrong answers; the O(n) version requires recognizing that you can recurse on INDEX ranges instead of array copies. Articulate this before coding.

Common mistakes

  • Slicing preorder — even with the inorder index map, slicing preorder reintroduces O(n^2).
  • Forgetting to increment p inside the recursion — easy when you switch from slicing to indexing.
  • Recursing on inorder[lo..mid-1] and inorder[mid+1..hi] but using preorder.slice() — defeats the purpose.

Follow-up questions

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

  • Construct from Inorder + Postorder (LC 106) — postorder[last] is root.
  • Construct from Preorder + Postorder (LC 889) — non-unique solutions.
  • Datadog-style: deserialize a metric tree from preorder + inorder serialized forms.

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 pre-iterate through preorder instead of recursing on slices?

Preorder visits root first, then left subtree fully, then right subtree fully. So a single index walking through preorder always points at the current root. No need to slice.

What if values aren't unique?

indexOf becomes ambiguous. The problem assumes uniqueness; in general, you'd need positional encoding.

Practice these live with InterviewChamp.AI

Drill Construct Binary Tree from Preorder and 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 →