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.