Construct Binary Tree from Preorder and Inorder Traversal
Given the preorder and inorder traversals of a tree with distinct values, rebuild the tree.
A way to picture it
Two witnesses describe the same family. The first always names a parent before their children (preorder), so they tell you who's in charge. The second lists everyone left to right (inorder), so they tell you who stands on which side of that parent.
How to approach it
The next preorder value is the root of the current range. Its position in inorder splits the range into left and right subtrees. Recurse left, then right.
Example
Input: {"preorder":[3,9,20,15,7],"inorder":[9,3,15,20,7]}. Output: [3,9,20,null,null,15,7].
Complexity: O(n) time and O(n) space. A hash map finds each root's inorder position in O(1).
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.