Construct Binary Tree from Preorder and Inorder Traversal
Rebuild a tree from preorder and inorder traversals with unique values.
Why does this pattern fit?
Restate the exact job
Rebuild a tree from preorder and inorder traversals with unique values.
Preorder chooses the root; inorder splits left and right subtrees.
O(n) time · O(n) space
Searching inorder on every call degrades to O(n²).
How to solve Construct Binary Tree from Preorder and Inorder Traversal
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Rebuild a tree from preorder and inorder traversals with unique values.
Why Trees & recursive traversal fits
Preorder chooses the root; inorder splits left and right subtrees.
State to maintain
A preorder index, inorder bounds, and value-to-index map.
Transition
Take the next preorder root and recursively build the inorder left and right ranges.
Time and space
O(n) time · O(n) space
Counterexample to the tempting mistake
Searching inorder on every call degrades to O(n²).
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.