10.5k 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

in DS
recategorized | 10.5k 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

+1
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.
+1
Yes, but search time won't affect the asymptotic complexity -- please see the updated link at bottom of the answer.
0
Here elements are 1,2,3,..n hence we can found element in O(1) time in In-oder traversal .

hence it leads to O(n) time complexity.

But if the element set is [1,n] not sequential then to find element it takes O(logn).

hence in this case time worst case time complexity will be O(nlogn).

am i right @Arjun sir

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/

by Veteran (420k points)
edited
0
See in this code we have to visit every node.

So, T.C.=$O\left ( n \right )$

right??
0
Here we have to check every element from postorder and for that element we have to search in inorder..

So for naive approach O(nlogn) time complexity is more intuitive.. But as explained in the answer it can be done in O(n).
0

why nlogn? I mean why logn need to be multiplied??

Even code is giving some internal error

Check :https://ideone.com/BBEIIJ

0
ma'am see the starting and ending part of answer..
0

@Verma Ashish

Can u tell me meaning of this line?

Last element in post order is the root of tree- find this element in inorder- logn time.

Only for this line it is taking log n , rt??

ckeck here this code working fine :) https://ideone.com/URDpMI

+1
Since it is a bst therefore inorder will be in sorted order so we can apply binary search on inorder (O(logn)). Let's say element is x then after finding x inorder will be splitted in two parts -- elements less than x form left subtree and elements greater than x goes to right subtree.

Recursively this procedure is applied on left subtree and right subtree also..

Thanks for the code :)
+1
yes, but why do we need binary search??

See, $T(n)=T(k)+T(n-k-1)$

here $T(k)$ will be left subtree and $T(n-k-1)$ will be right subtree. So, why extra binary search will be needed?? We need to traverse every node, na??
+1

Yes.. you are right..here we don't need searching..

In answer also this thing is mentioned-

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), (6th 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)

0

yes, that is what I got.

Can u got why prev code is giving internal error?? If u got it, plz tell me too.

0
I didn't get that..

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).

Link for reference of ranges:

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

by (393 points)
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).

0
thank you for link
0
great

Here is the Stack's based Iterative solution that works in O(n) time..

Construct BST from given Postorder Traversal.  ( traverse given postorder in reverse)

1. Create an empty Stack.
2. Start from last element and make it as root. Push it into the stack.
3. If the next value  is greater than stack's top value, make it as right child of Stack's top node. Push the node to the stack.
4. Continue popping while Stack is not empty and the next value is less than Stack's top value. Make this value as left child of last popped node. Push the new node to the stack.
5. Repeat steps 3 and 4 until no item is left in given postorder array of elements.

We can also perform similar technique for preorder,

Construct BST from given Preorder Traversal

1. Create an empty stack.
2.  Make the first value as root. Push it to the stack.
3. Keep on popping while the stack is not empty and the next value is greater than stack’s top value. Make this value as the right child of the last popped node. Push the new node to the stack.
4.  If the next value is less than the stack’s top value, make this value as the left child of the stack’s top node. Push the new node to the stack.
5. Repeat steps 3 and 4 until no item is left in given preorder array of elements.

Since,every item is pushed and popped only once. So at most 2n push/pop operations are performed for n elements.Therefore, time complexity is O(n).

Thus for any P as postorder traversal, in order to determine the unique BST, the most efficient algorithm takes O(n).

by Active (2.5k points)
0
@Meghna-How your stack method works?

Consider I have order 1, 7, 5, 50, 40, 10

My next element to be considered in postorder is 1.

stack contents are 7->5(from top to bottom)

Now, 1 will cause the stack to become empty as per your algorithm

how 1 will be placed in the bst then?
+1

@Ayush Upadhyaya when you have element 1 left in the postorder and stack contains 7->5 (top to bottom) than pop out all the elements from stack (i.e pop 7 then pop 5) and make 1 as left child of last popped element i.e 5.

0

Okay convinced!. But this method will always guarantee that the bst I will get is "unique" for the postorder traversal given?

+1

I think the uniqueness of the tree is determined if we're able to separate the left sub tree and the right tree with the given tree traversals. In-order does exactly the same, by segregating the LST, then root then RST.So with any given order (pre-order, post-order, level order), we always know where to place the node, creating no ambiguity. So as per this method is concerned, we are always sure about where to place the node, making it generate a unique tree with no ambiguity.

Proof: why In-order (+ pre, post or level) generates unique tree. (though very complex to understand):https://stackoverflow.com/questions/30556590/how-does-inorderpreorder-construct-unique-binary-tree

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.
by (265 points)
–1 vote
Answer is c as inorder is sorted u can do a binary search
by Active (2.5k points)