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 549 students.

Show answer

Correct answer: B

The worked solution is available to enrolled students.

Video solution available to enrolled students.

Explore the full course: Iocl Engineers Officers Grade A Paper 2