Reconstruct BST from preorder
You are given the preorder traversal of a binary search tree (all values distinct). Reconstruct the BST and return its postorder traversal, without explicitly building node objects if you prefer. Use the BST property: in the preorder sequence the first value is the root, the next run of smaller values is the left subtree, and the remaining values (each less than an upper bound) form the right subtree, so a single linear scan with a moving index and an upper-bound argument reconstructs it in O(n). Return the postorder list.
bst_preorder_to_postorder(preorder: list[int]) → list[int][[8,5,1,7,10,12]]out[1,7,5,12,10,8]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[8,5,1,7,10,12]][1,7,5,12,10,8]not run yetsample