23,515 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

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)

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

edited
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.
Yes, but search time won't affect the asymptotic complexity -- please see the updated link at bottom of the answer.
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

@Arjun sir as it is mentioned that it is a bst so by sorting elements of postorder traversal we can find inorder .

So from inorder and postorder we can construct unique bst.

Where i am getting wrong?

@Verma Ashish

PreOrder, PostOrder or InOrder all will takes O(n) time.

because, here we traverse every node once.

right??

Yes. Time complexity of preorder, inorder and postorder traversals is O(n).

But this question is about constructing unique bst from inorder and postorder
So, what will be difference??
edited

Here we have to look into both post order and inorder for making decision for a node.. And I'm not able to understand the code given in the answer..

Even if it is not bst and we have inorder and postorder then also there is a solution given here which uses hashing and construct tree in O(n)

@Verma Ashish

Code is nothing but simple a BST creation. Isnot it??

In hashing search time is O(1), good than other algo. but how create an BST with hashing?? Can u plz give the hint.

Code is nothing but simple a BST creation. Isnot it??

Yes.. but it is difficult for me to analyze time complexity of given code.

By using efficient procedure we can reduce search time..which is done on geeksforgeeks..(by using hashing). In simple searching an element from inorder of a bst can be found in O(logn). (O(n) if it is not bst)

I have no idea about there implimentation(hashing and all..)   (｡•́︿•̀｡)

See in this code we have to visit every node.

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

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

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

Even code is giving some internal error

Check :https://ideone.com/BBEIIJ

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

@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

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 :)
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??

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)

yes, that is what I got.

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

I didn't get that..
worst case-- how is it n * O(logn) ?? we are just performing binary search once in the Inorder list to find the root !
@Verma Ashish I am not getting the fact that why we are mentioning inorder continuously what role is that playing here??
sir if we sort the post order then time complexity will become nlogn

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/

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

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

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

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?

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

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

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.
Answer is c as inorder is sorted u can do a binary search