6,659 views

5 Answers

9 votes
9 votes

Consider this tree. 

If its In-order and Post-order traversal is given then you have to traverse whole in-order list linearly for searching root. It will take O(n^2) times.

But the trick here is that, Since In-order traversal is sorted hence we can directly apply Binary search, instead of performing the linear search, that reduces the time complexity to O(nlogn). So answer is O(nlogn).

edited by
7 votes
7 votes

i/p : inorder and postorder for BST are given

o/p : unique BST

Algorithm : postorder basically tells us the Root and inorder basically tells us right and left part of root.

Scan postorder from right to left. first element from left would be ROOT of tree  and then search this node value in inorder , after getting item , left part of that item would be left subtree elements of ROOT and right part of that node will be right subtree elements of ROOT , then for left subtree and right subtree construction again run the same procedure in recursive manner.

If given tree is BT then to search roots , TC would be O(n) linear search.

but if it's BST , inorder is sorted so to search directly apply binary search so complexity=O(logn)

for Postorder for each and every element from left we have to apply same procedure so

TC for BT=O(n2)

TC for BST=O(nlogn)

1 votes
1 votes

for given inorder ,post order or inorder, preorder to create BST it takes O(n2) . because n time linear search to find out LST and RST (worst case). if inorder is not sorted

and but if inorder sorted than it takes O(nlogn). so here Bidefault take inorder is not sorted so final Answer is O(n2)  is correct.  option 3 is correct.

Related questions

2 votes
2 votes
3 answers
2