##### 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?

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.

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

binarytreefrom inorder and postorder traversal: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 buildbinary search treeusing inorder and postorder/preorder travarsal.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)