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.

asked
Apr 2
in DS
Lakshman Patel RJIT
107 views