recategorized by
824 views
1 votes
1 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.
recategorized by

1 Answer

1 votes
1 votes

Option B

The algorithm of finding a number in inorder traversal using binary search is just inefficient. As tree given is a Binary Search Tree and postorder traversal is given, we know last element is the root.


Start from last element down to first element (that is read postorder traversal in reverse), and construct a BST like you normally do following the BST property i.e. if element is less than root, add it as left node and if the element is greater than root add it on right. Do this recursively, by passing the correct ranges in which the number should lie (fulfilling BST property). It will be the required BST. This takes traversing the postorder traversal once O(n) creating n recursive calls doing O(1) work of adding one node at a time. 

And I am sure you have applied this already with preorder in many questions. Given the preorder of a BST, you just parse it from left to right and create a unique BST with hand in O(n) time (without using quicksort and pivot). 

https://gateoverflow.in/458/gate2008-46

Answer:

Related questions

2 votes
2 votes
2 answers
1
admin asked Apr 2, 2020
1,064 views
A hash table with $10$ buckets with one slot per bucket is depicted. The symbols, $S1$ to $S7$ are initially emerged using a hashing function with linear probing. Maximum...
2 votes
2 votes
2 answers
2
admin asked Apr 2, 2020
783 views
A full binary tree with $n$ non-leaf nodes contains$\log_ 2 n$ nodes$n+1$ nodes$2n$ nodes$2n+1$ nodes
1 votes
1 votes
1 answer
3
admin asked Apr 2, 2020
685 views
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. Total time required for this is$\Theta (\lo...