Skip to main content

105. Construct Binary Tree from Preorder and Inorder Traversal

medium

Rebuild a binary tree from its preorder and inorder traversals. Tests the deep relationship between traversal orders — preorder gives you the root, inorder splits the subtrees.

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

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.
  • Each value of inorder also appears in preorder.
  • preorder is guaranteed to be the preorder traversal of the tree.
  • inorder is guaranteed to be the inorder traversal of the tree.

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]

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Preorder starts with the root. Find that root in inorder.

Hint 2

Everything left of that index in inorder is the left subtree; everything right is the right subtree.

Hint 3

Recurse. Build a value->index map of inorder once to make the lookup O(1).

Solution approach

Reveal approach

Recursive partition with a position map. Precompute inorderIndex: a hash map from inorder value -> its index. Maintain a global preorderPos pointer starting at 0 (the next root to consume from preorder). Helper build(left, right) on the inorder range: if left > right return null; rootVal = preorder[preorderPos++]; idx = inorderIndex[rootVal]; node = new TreeNode(rootVal); node.left = build(left, idx - 1); node.right = build(idx + 1, right); return node. Initial call: build(0, n - 1). O(n) time (each node built once, O(1) lookup), O(n) space for the map and recursion.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • dfs
  • recursion
  • tree-construction

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Construct Binary Tree from Preorder and Inorder Traversal and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →