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 Sam K., 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

More Trees practice problems

See all Trees problems →