You are given the postorder traversal, P, of a binary search tree on the n…
GATE · 2008 · CS
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., 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?
- A.
O(Logn)
- B.
O(n)
- C.
O(nLogn)
- D.
none of the above, as the tree cannot be uniquely determined.
Attempted by 585 students.
Sign up free to check your answer
Sign up freeLoading lesson…