Construct Binary Tree from Preorder and Inorder Traversal
MediumTrees
You get two arrays of the same distinct values: preorder, the order a preorder walk (node, left subtree, right subtree) visits a binary tree, and inorder, the order an in-order walk (left subtree, node, right subtree) visits the same tree. Build that tree and return its root.
On this page the tree you return is written in level order, top to bottom and left to right, with null where a child is missing: [6, 3, 8, 1] is 6 with children 3 and 8, and 3 with a left child 1.
Examples
Input: preorder = [5, 2, 1, 8, 9], inorder = [1, 2, 5, 8, 9] Output: [5, 2, 8, 1, null, null, 9]
5 comes first, so it is the root. In inorder, 1 and 2 sit left of it and 8 and 9 right of it.
Input: preorder = [7], inorder = [7] Output: [7]
One value makes a tree of one node.
Constraints
1 ≤ preorder.length ≤ 3000, andinorderhas the same length.-3000 ≤ preorder[i], inorder[i] ≤ 3000- The values are distinct, and both arrays come from the same tree.
Stuck?
Hint 1
The first value of preorder is the root. Find it in inorder: the values before it form the left subtree, and the values after it form the right subtree.
Hint 2
The size of the left part tells you how many values after the root in preorder belong to the left subtree; the rest belong to the right. Recurse on both parts, and keep a Map from value to index in inorder so each lookup is O(1).
The idea
The first value in preorder is the root, and its place in inorder splits the rest: values to its left form the left subtree and values to its right form the right one. Preorder lists a node's whole left subtree before its right one. So if the tree is built left side first, the next unused value in preorder is always the root of the subtree being built.
Time O(n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
Searching inorder for each root would cost O(n) each time. A Map from value to index makes each lookup constant, which works because the values are distinct.
function buildTree(preorder, inorder) { const position = new Map(inorder.map((value, i) => [value, i])); let next = 0; const build = (low, high) => { if (low > high) return null; const root = new TreeNode(preorder[next++]); const mid = position.get(root.val); root.left = build(low, mid - 1); root.right = build(mid + 1, high); return root; }; return build(0, inorder.length - 1);}The trap
Building the right side before the left takes values from preorder in the wrong order. A node with only one child still comes out right, because the empty side takes no value. Once a node has both children, the right side takes the value that is really the left subtree's root, and the tree goes wrong from there.
function buildTree(preorder, inorder) { const position = new Map(inorder.map((value, i) => [value, i])); let next = 0; const build = (low, high) => { if (low > high || next >= preorder.length) return null; const root = new TreeNode(preorder[next++]); const mid = position.get(root.val); // builds the right subtree first, but preorder lists the left one first root.right = build(mid + 1, high); root.left = build(low, mid - 1); return root; }; return build(0, inorder.length - 1);}