Project ForgeData Structures
Trees
GATE 2008
Hard
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Θ(log n)
- Θ(n)
- CΘ(n log n)
- Dnone of the above, as the tree cannot be uniquely determined
Explanation
The last element of the postorder sequence is the root; since it's a BST on a known key range, all smaller values (forming a contiguous prefix by BST property) belong to the left subtree and the rest to the right — this range-based partitioning can be done recursively in O(1) work per node, giving Θ(n) total.
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.