You are given the preorder and the inorder traversal of a binary tree with unique values. Rebuild the tree.
DSA Animator › DSA Revision › Tree › Construct Binary Tree from Preorder and Inorder Traversal
Remember: preorder gives the root, inorder gives the split. Build left before right, so the preorder pointer stays in sync. The video solves Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105, Medium) with the Divide and Conquer pattern from the Tree topic, and you can replay every step in the interactive Construct Binary Tree from Preorder and Inorder Traversal animation.
You are given the preorder and the inorder traversal of a binary tree with unique values. Rebuild the tree.
For preorder 3, 9, 20, 15, 7 and inorder 9, 3, 15, 20, 7, the tree is 3, with children 9 and 20, where 20 has children 15 and 7.
Trying every possible tree shape and checking both traversals is hopeless. The two traversals carry complementary information, and together they fix the tree.
The first value of the preorder is always the root. Find that root in the inorder, and everything to its left belongs to the left subtree. Everything to its right belongs to the right subtree. The size of the left part tells you how many preorder values belong to the left subtree. Use a hash map from value to inorder index, so each lookup is O of 1.
Preorder starts with 3, so 3 is the root. In the inorder, 3 is at index 1, so only 9 is on its left, and 15, 20, 7 are on its right. The next preorder value, 9, is the root of the left subtree, and it has no children. Then 20 is the root of the right subtree. 20 sits between 15 and 7 in the inorder, so 15 is its left child and 7 is its right child. The tree is rebuilt: 3, 9, 20, 15, 7.
In code, fill a map from each inorder value to its index. Keep a pointer into the preorder that moves forward each time a node is created. The helper takes an inorder range, creates the root from the preorder pointer, and splits at the root index. It builds the left range first, then the right range, because that is preorder order. Each value is placed once, so it's O of n time.
Remember: preorder gives the root, inorder gives the split. Build left before right, so the preorder pointer stays in sync.