-
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 ?
-
- Θ (log n)
- Θ (n)
- Θ (n log n)
- None of the above, as the tree cannot be uniquely determined
- Θ (log n)
Correct Option: B
To construct a BST from post order we also require in-order traversal since given the elements are 1 2.......n. So their sorted order would be in order. Using both BST can be constructed in a linear scan. So it will take only 4n time.
