edited by
38,623 views
129 votes
129 votes

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?

  1. $\Theta(\log n)$
  2. $\Theta(n)$
  3. $\Theta(n\log n)$
  4. None of the above, as the tree cannot be uniquely determined
edited by

6 Answers

0 votes
0 votes

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:

Related questions

32 votes
32 votes
2 answers
2
Ishrat Jahan asked Oct 29, 2014
12,456 views
How many distinct BSTs can be constructed with $3$ distinct keys?$4$$5$$6$$9$