Construct Binary Tree From Preorder and Inorder Traversal
The problem
Rebuild a binary tree from valid preorder and inorder arrays containing the same distinct values. Return the root.
Example
preorder = [5, 2, 9], inorder = [2, 5, 9] → root 5 with children 2 and 9
Need a hint?
Preorder identifies the root; its inorder position splits the subtrees.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Map each value to its inorder index. Consume preorder with one advancing cursor. For an inorder interval, take the next preorder value as root, recursively build the interval to its left, then the interval to its right. Empty intervals produce null. Avoid repeatedly slicing arrays.
Complexity
O(n) time and O(n) space including the index map and recursion.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.