The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+45 votes
7.4k 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

asked in DS by Veteran (59.5k points)
recategorized by | 7.4k 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.
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

5 Answers

+51 votes
Best 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).$

(Stirling's Approximation)

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/

answered by Veteran (357k points)
edited by
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.

0
As we have given elements of BST are 1 to n. Inorder of a BST is sorted. So, inorder traversal will be 1,2,3,4....n
+6 votes

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/

answered by (293 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
+5 votes

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

answered by Active (1.4k 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? 

0

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

This may also help:https://stackoverflow.com/questions/33062228/why-it-is-impossible-to-construct-binary-tree-with-pre-order-post-order-and-lev

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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,645 questions
46,729 answers
140,391 comments
58,088 users