GATE CSE 2008 | Question: 46

Question

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?

• A. $\Theta(\log n)$
• B. $\Theta(n)$
• C. $\Theta(n\log n)$
• D. None of the above, as the tree cannot be uniquely determined

Comments

Yes, but search time won't affect the asymptotic complexity -- please see the updated link at bottom of the answer.

---

Here elements are 1,2,3,..n hence we can found element in O(1) time in In-oder traversal .

hence it leads to O(n) time complexity.

But if the element set is [1,n] not sequential then to find element it takes O(logn).

hence in this case time worst case time complexity will be O(nlogn).

am i right @Arjun sir

---

No in any case it follows BST property so O(N) will be the answer

Here is very easy and intuitive explanation

https://gateoverflow.in/458/gate-cse-2008-question-46?show=406177#a406177

Answer 1

Very Easy and Intuitive solution:

Observation for postorder finding its left and right subtree elements need O(1) because of the fact that left subtree element is always less than the root whereas the right is greater.

Here is the Program of Time Complexity O(n)

credit: striver
https://www.youtube.com/watch?v=UmJT3j26t1I

Answer 2

Answer is c as inorder is sorted u can do a binary search