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 to beat.
Example
- preorder = [8,5,1,7,10,12] → BST with root 8, left subtree {5,1,7}, right subtree {10,12}.
asked …