GATE CS 2008 Q46 — Binary Search Trees

To reconstruct a Binary Search Tree (BST) from its postorder traversal $P$ of $n$ elements:

1. Uniqueness: For any BST, the inorder traversal is always the sorted order of its elements. Since we are given the postorder traversal and can obtain the inorder traversal by sorting (or we already know it is $1, 2, \dots, n$), the BST is uniquely determinable.
2. Efficiency:
   • A naive recursive approach that searches for the division point between the left and right subtrees takes $O(n^2)$ time in the worst case (e.g., for a skewed tree).
   • We can optimize this to $\Theta(n)$ time by traversing the postorder array from right to left (which yields the sequence: $\text{Root} \rightarrow \text{Right} \rightarrow \text{Left}$) and maintaining a valid numerical range $[\text{min}, \text{max}]$ for each node.
   • Since each element is visited and processed a constant number of times, the overall time complexity is $\Theta(n)$.

Therefore, the time complexity of the most efficient algorithm is $\Theta(n)$.