Construct a binary tree from inorder + preorder

Medium

Problem

Given the preorder and inorder traversals of a binary tree with unique values, rebuild the tree and return its root.

Example 1

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

Also asked as: Construct Binary tree from Inorder and preorder traversal

Test cases

Case 1

Input:    [3,9,20,15,7], [9,3,15,20,7]
Expected: [3,9,20,null,null,15,7]

Case 2

Input:    [-1], [-1]
Expected: [-1]

Case 3

Input:    [1,2,3], [2,1,3]
Expected: [1,2,3]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Recursion with an index map for inorder

Time O(n)Space O(n)

The next preorder value is the current root; its position in inorder splits the array into left and right subtrees.

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