Construct a binary tree from inorder + preorder
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]
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);}