Construct optimal BST from traversals

Problem Given the preorder traversal of a binary search tree, reconstruct the BST.

Input / Output

• Input: int array preorder (a valid BST preorder).
• Output: root of the reconstructed BST.

Constraints

• Up to 10^5 nodes; the expected solution is O(n) — repeatedly inserting each key (O(n log n) average, O(n^2) worst) is the naive answer the interviewer wants you to beat.

Example

• preorder = [8,5,1,7,10,12] → BST with root 8, left subtree {5,1,7}, right subtree {10,12}.

Expected approach

• Recursive bounds method: consume values in preorder order, passing (min, max) limits; a value outside the current bounds belongs to an ancestor's other subtree. Each node is visited once → O(n) time, O(h) stack. An explicit-stack iterative version avoids recursion. If both inorder and preorder are given (general binary tree variant), use the inorder-index map for O(n).