##### Complexity of constructing BST

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, …, 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?
(A) O(Logn)
(B) O(n)
(C) O(nLogn)
(D) none of the above, as the tree cannot be uniquely determined.

here answer is given as o(n) but to find inorder we have atleast to do sorting and best algorithm can find sorting o(nlogn) answer must be C?

Sumit Verma
4 May 2017 02:06 pm

It is given in the question that tree is a binary search tree (BST) so we need not to perform sorting to get inorder traversal. There are 'n' elements from 1,2....n, so this sequence is inorder traversal.
Now for you have both postorder and inorder traversals, so you can form unique tree in O(n) time.

Abhishek
4 May 2017 11:52 am
how we can get it in O(n) time if we have postorder and inorder??
8 May 2017 04:07 pm

Note:
1. You have given n elements from 1 to n.
2. In BST(binary search tree), inorder traversal is always sorted ordered.

Algorithm to build binary tree from inorder and postorder traversal:

1. Take the last element from postorder as root element of binary tree. This takes O(1) time.
2. Perform binary search on given sequence 1 to n to find that element in inorder traversal. This takes O(log n) time.
3. Now divide inorder traversal using that element using pivot selection.
4. Repeat for both split part. This takes T(k) and T(n-k-1) time.

The recurrence relation would be T(n) = T(k) + T(n-k-1) + O(log n) = O(n log n). This is time complexity to build binary tree using inorder and postorder/preorder traversal.

As you have given that tree is binary search tree, so there is no need to perfrom binary search. Simply, we take pivot and split given list from 1 to n element. The recurrence relation would be T(n) = T(k) + T(n-k-1) + O(1) = O(n). This is time complexity to build binary search tree using inorder and postorder/preorder travarsal.

Sparsh
4 Aug 2017 02:51 pm

See - If we have preorder[] and ok inorder[] as well from (1,2,....,n) so we need to look for each element of preorder[] in inorder[] array to decide to which node of preorder[] we have to make it right or left child(in inorder[] using Binary Search).. right, so is it not like this - O(n)*O(logn) = O(nlogn)