You are given the postorder traversal, P, of a binary search tree on the n…

PYQ GATE 2008

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?

  1. A.

    O(Logn)

  2. B.

    O(n)

  3. C.

    O(nLogn)

  4. D.

    none of the above, as the tree cannot be uniquely determined.

Attempted by 694 students.

Sign up free to check your answer

Sign up free

Explore the full course: Data Structures

Loading lesson…