edited by
38,586 views
129 votes
129 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
edited by

6 Answers

Best answer
134 votes
134 votes

Correct Answer: B

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/

edited by
45 votes
45 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/

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

7 votes
7 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.
Answer:

Related questions

32 votes
32 votes
2 answers
2
Ishrat Jahan asked Oct 29, 2014
12,444 views
How many distinct BSTs can be constructed with $3$ distinct keys?$4$$5$$6$$9$