Rebuild a binary search tree from its postorder traversal in linear time

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

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

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

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

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.