DSA problem
Construct Binary Tree from Preorder and Inorder Traversal
Given two arrays preorder and inorder representing the preorder and inorder traversals of a binary tree with distinct values, reconstruct and return the tree. The two traversals together uniquely determine the tree.
The key insight is the interplay between the two sequences. The first element of preorder is always the root of the current subtree — that is what makes preorder "preorder". Once we know the root's value, we can find its position in inorder. Everything to the left of that position in inorder belongs to the left subtree; everything to the right belongs to the right subtree.
Crucially, the number of elements in the left subtree (call it k) tells us how to slice preorder too: the next k elements of preorder are the preorder traversal of the left subtree, and the rest are the preorder traversal of the right subtree. So we can recursively build both subtrees.
A naive implementation that slices arrays at each step and scans inorder for the root each time costs O(n²). The optimal implementation builds a hashmap value → index for inorder once (O(n)), then uses index-based recursion and a shared preorder index that is incremented as we consume roots. Building the left subtree first ensures the consumption order matches the preorder layout. Total work is O(n) time and O(n) space (the map plus recursion).
Examples
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7][3,9,20,null,null,15,7]preorder = [-1], inorder = [-1][-1]preorder = [1,2,3], inorder = [3,2,1][1,2,null,3]Constraints
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- All values in both preorder and inorder are unique.
- preorder and inorder consist of unique values.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.