You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1, 2, \dots, n$. You have to determine the unique binary search tree that has $P$ as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
- $\Theta(\log n)$
- $\Theta(n)$
- $\Theta(n\log n)$
- None of the above, as the tree cannot be uniquely determined