6.3k views

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 | 6.3k views
0
here we are assuming that INORDER is separately given?

because if we are sorting postorder to get inorder, then it would be counted in the TC itself. adding another factor of O(n \sqr)
0

I also thought that but since here we have "n elements from 1,2,.....,n".....creating inorder can be done in Θ(n) time

0
First of all very good analysis by @Arjun Sir.

But i would like to mention few points. Question is saying n elements their value could be anything. So extra log(n) time is required in searching. But if elements are numbers from 1,2,..,n then no need for search.
0
Yes, but search time won't affect the asymptotic complexity -- please see the updated link at bottom of the answer.

Last element in post order is the root of tree- find this element in inorder- $\log n$ time.
Now as in quick sort consider this as pivot and  split the post order array into 2- possible because all elements smaller than pivot goes to left and all elements larger than pivot goes to right and suppose we have x elements smaller than pivot, these elements will be same in both inorder as well as postorder (order may change). We already got the root, now left child is the left split and right child is the right split.

So, doing this recursively gives time complexity of this approach as
$$T(n) = T(k) + T(n-k-1) + \log n$$

Solving would give $T(n) = O(n \log n)$ in worst case, by putting $k=0$ and shown at bottom.

But searching for an element in the inorder traversal of given BST can be done in $O(1)$ because we have $n$ elements from $1..n$ so there is no need to search for an element- if last element in post order is say $5$ we take it as root and since $4$ elements $(1..4)$ are smaller we split the post order array in to two- (first $4$ elements), ($6$th element onward) and solve recursively. Time complexity for this would be

$$T(n) = T(k) + T(n-k-1) + O(1)$$

which gives $T(n) = O(n).$

Since we know that all elements must be traversed at least  once, $T(n) = \Omega(n)$ also and so $$T(n) = \Theta(n).$$ The following code is doing this.

//Install graphviz (sudo apt-get install graphviz on Ubuntu) to view output tree
#include<stdio.h>
#include<stdlib.h>
struct tree
{
struct tree* left;
struct tree* right;
int x;
};
struct tree* makenode(int x)
{
struct tree * root =  malloc(sizeof(struct tree));
root -> x = x;
root -> left = root -> right = NULL;
return root;
}

struct tree* makeBST(int *post, int start, int n, int inorder){
if(n <= 0)
return NULL;
int pivot = post[start + n -1];
struct tree * root = makenode(pivot);
root -> left = makeBST(post, start, pivot-1 - inorder, inorder );
root -> right = makeBST(post, pivot - inorder - 1, n - (pivot - inorder), pivot);
return root;
}
void preorder(struct tree* node)
{
if(node == NULL)
return;
printf("%d ", node->x);
preorder(node->left);
preorder(node->right);
}
void printdot(struct tree* node, FILE * f)
{
if(node == NULL)
return;
if(node-> left != NULL)
{
fprintf(f, "%d -- %d;\n", node->x, node->left->x);
}
if(node-> right != NULL)
{
fprintf(f, "%d -- %d;\n", node->x, node->right->x);
}
printdot(node->left, f);
printdot(node->right, f);
}

int main(){
int i, n, *a;
printf("Enter n: ");
scanf("%d", &n);
a = malloc(n * sizeof(int));
printf ("Enter post order traversal: ");
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
struct tree * tree = makeBST(a, 0, n, 0);
printf("Pre order traversal is : ");
preorder(tree);
printf("\n");
FILE * f = fopen("tree.dot", "w");
fprintf(f, "graph tree { \n");
printdot(tree, f);
fprintf(f, "}\n");
fclose(f);

#if defined(__linux__) || (defined(__APPLE__) && defined(__MACH__) || (defined (__gnu_linux__)) )
system("dot -Tpng tree.dot -o output.png; eog output.png");
#endif

}

$$T(n) = T(k) + T(n-k-1) + \log n$$

Solving would give $T(n) = O(n \log n)$, by putting $k=0$,
$T(n) = T(0) +T(n-1) + \log n, \\\implies T(n) = O(1)+ \log n + \log (n-1) + \log (n-2) + \dots + \log 1\\\implies T(n) = n + \log n! \\\implies T(n) = O(n \log n).$

PS: Even for a general BST, given a post order traversal, we can construct the BST in $O(n)$ more stricter than $O(n \log n)$ derived above and this matches $\Omega(n)$ and hence we do have an $\Theta(n)$ algorithm. This algorithm can be seen at below link
https://www.geeksforgeeks.org/construct-a-binary-search-tree-from-given-postorder/

edited by
0
Answer should be D. As inorder traversal is not given, and thus tree can not be determined uniquely.

Please tell me if I am wrong.
0

@Arjun sir as we can construct a unique bst just from its postorder traversal then why we need to look at inorder traversal at all because by looking at inorder traversal will increase the complexity when a number are not 1,2,3.....n because in that case, we will have to search an element in inorder traversal using binary search that will take logn time as in that case location will not be value of an element -1 . So can't we just use postorder and use the above algorithm so that in general case also complexity will be same i.e o(n)????

0

@abk1115

we can construct a unique bst just from its postorder traversal

who told this?

0
What is the answer? b or c?
0
What i can understand from above is that for this problem answer is 0(n) because inorder search is 0(1).And every time when we choose root and call for left and right ,right will be empty tree and left will have n-1 nodes.

But for general case you mentioned it is nlogn. but the geeksforgeeks has given 0(n) solution for pre order.And they claim that same can be modified to handle postorder also in 0(n).Please help here @Arjun sir
0
i think it should be "split inorder array into two parts" in second line...
0
@vinay125

Inorder traversal of a BST is always sorted order.So , unique tree can be constructed.
0
Exactly same point.
0
Yes , we can.
+1

@Arjun Sir, the code seems to fail on the case of P = [1,3,5,4,2]. I modified the start of right subtree as start + (n-(pivot-inorder)) and set a check for start at the beginning of the function to fix it.

take any example and try to create BST by adding one by one element in given sequence(preorder then first to last element and postorder then reverse) everytime you ended up with correct BST. Bcoz here by adding we follow two rules 1)we will compare value(BST property) 2) by following sequence we are sure that created tree will have same pre/postorder as given

so Time Complexity of creating such BST from given pre/postorder is O(n) all time.

I don't think it's a very difficult question. 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).

http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-recursion/

0
[if we are building a tree from given list], then

for inserting 'n' nodes in a binary search tree in avg case we need O(nlogn) time,

the complexity of traversing post order list will be O(n), but inserting will have separate complexity of O(nlogn).

correct me if i am wrong..
0

As far as I remember, idea was to use BST min max algorithm to recursively put values into the BST. It passes ranges of max and min values along with root to insert an element. You can refer to the link given in post or this link:
http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
(2nd method in this post) -> O(n) time.
And I felt like this is what we intuitively do while solving GATE questions on BST instances. If this doesn't make sense, there is also an O(n) stack solution in which you can actually see why it's not O(n^2).

+1 vote
–1 vote
Answer is c as inorder is sorted u can do a binary search