Rebuild a binary search tree from its postorder traversal in linear time
Company: Cubist
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given the postorder traversal of a binary search tree (BST) whose values are all distinct. Rebuild the tree and return its preorder traversal.
In a BST, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. A postorder traversal lists a node's left subtree, then its right subtree, then the node itself. The postorder traversal of a BST with distinct values determines the tree uniquely, so the preorder traversal you return is unique.
The interviewer required the reconstruction to run in $O(n)$ time, where $n$ is the number of nodes.
### Function Signature
```python
def bst_preorder_from_postorder(postorder: list[int]) -> list[int]:
```
### Rules
- `postorder` is guaranteed to be the postorder traversal of some BST with distinct values; you do not need to validate it.
- Return the preorder traversal of that BST: a node, then its left subtree in preorder, then its right subtree in preorder.
- The returned list contains the same values as `postorder`, each exactly once.
### Constraints
- `1 <= len(postorder) <= 10^4`
- `-10^9 <= postorder[i] <= 10^9`, and all values are distinct.
- The tree may be completely skewed, so its height can equal `len(postorder)`.
- Required time complexity: $O(n)$.
### Examples
**Example 1**
```text
Input: postorder = [1, 3, 2, 5, 7, 6, 4]
Output: [4, 2, 1, 3, 6, 5, 7]
```
The tree has root `4`. Its left child is `2`, with children `1` and `3`; its right child is `6`, with children `5` and `7`.
**Example 2**
```text
Input: postorder = [2, 4, 3, 8, 7, 5]
Output: [5, 3, 2, 4, 7, 8]
```
The root `5` has left child `3` (with children `2` and `4`) and right child `7`, whose only child `8` is its right child.
**Example 3**
```text
Input: postorder = [3, 2, 1]
Output: [1, 2, 3]
```
The root is `1`, `2` is its right child, and `3` is the right child of `2`.
Overview: Rebuild a binary search tree with distinct values from its postorder traversal and return the rebuilt tree's preorder traversal. The problem tests BST ordering properties, traversal orders, and meeting a strict O(n) time bound on inputs that include deeply skewed trees.
You are given `postorder`, the postorder traversal of a binary search tree (BST) whose values are all distinct. Rebuild the tree and return its preorder traversal.
In a BST, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. A postorder traversal lists a node's left subtree, then its right subtree, then the node itself. A preorder traversal lists a node, then its left subtree in preorder, then its right subtree in preorder. The postorder traversal of a BST with distinct values determines the tree uniquely, so the preorder traversal you return is unique.
Implement `bst_preorder_from_postorder(postorder)`:
- `postorder` is guaranteed to be the postorder traversal of some BST with distinct values; you do not need to validate it.
- Return the preorder traversal of that BST as a list. It contains the same values as `postorder`, each exactly once.
- The reconstruction must run in O(n) time, where n is the number of nodes.
### Constraints
- `1 <= len(postorder) <= 10^4`
- `-10^9 <= postorder[i] <= 10^9`, and all values are distinct.
- The tree may be completely skewed, so its height can equal `len(postorder)`.
- Required time complexity: O(n).
- Every value fits in a signed 32-bit integer (no value can exceed 2^31-1), so a 32-bit `int` is sufficient in Java and C++.
### Example 1
```text
Input: postorder = [1, 3, 2, 5, 7, 6, 4]
Output: [4, 2, 1, 3, 6, 5, 7]
```
The root is `4`. Its left child is `2`, with children `1` and `3`; its right child is `6`, with children `5` and `7`.
### Example 2
```text
Input: postorder = [3, 2, 1]
Output: [1, 2, 3]
```
The root is `1`, `2` is its right child, and `3` is the right child of `2`.
Constraints
- 1 <= len(postorder) <= 10^4
- -10^9 <= postorder[i] <= 10^9, and all values are distinct
- postorder is guaranteed to be the postorder traversal of some BST with distinct values; no validation is needed
- The tree may be completely skewed, so its height can equal len(postorder)
- Required time complexity: O(n)
- Every value fits in a signed 32-bit integer (no value can exceed 2^31-1)
Examples
Input: ([1, 3, 2, 5, 7, 6, 4],)
Expected Output: [4, 2, 1, 3, 6, 5, 7]
Explanation: Source Example 1: complete balanced tree, root 4, left child 2 (children 1 and 3), right child 6 (children 5 and 7).
Input: ([2, 4, 3, 8, 7, 5],)
Expected Output: [5, 3, 2, 4, 7, 8]
Explanation: Source Example 2: root 5, left child 3 with children 2 and 4, right child 7 whose only child 8 is a right child.
Hints
- The last element of a postorder traversal is the root, and every other value belongs to the left or right subtree purely by how it compares with the root.
- Repeatedly scanning a subarray to find where the left subtree ends costs O(n^2) on a skewed tree; the O(n) requirement asks you to place each value without rescanning earlier work.
- The tree can be as tall as n, so check how your approach behaves on a fully skewed input, both in running time and in recursion depth.