Construct Binary Tree from Preorder & Inorder – Solution & Complexity
Solution Walkthrough
1. Recognize the Pattern
The key pattern is: the first element of any preorder slice is always that subtree's root, and looking up that value's position in the corresponding inorder slice splits the remaining nodes into the left and right subtrees.
2. Build the Algorithm
Advance one state transition at a time. Mark or update state before exploring dependent work.
3. Check Edge Cases
Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.
4. Solution and Complexity
Time: O(n) — a hash map lookup gives each value's inorder index in O(1), so every node is built exactly once. Space: O(n) for the value-to-index map plus O(h) recursion stack (O(n) worst case on a skewed tree).
All 5 languages below run and submit against the remote judge for this problem — Java/Go/Rust use the same real TreeNode structural-type support the judge added for the rest of the linked-list/tree track.
