Time complexity

Question

To construct binary search tree either from preorder or postorder what is the efficient time complexity ?

can we construct unique BST along with post and preorder ?Then what is the significance of using PRE+INORDER or POST+INORDER

Comments

https://gateoverflow.in/36610/complexity-construct-binary-inorder-postorder-traversal

---

We can do in O(n) time complexity ...using help of partition function

Answer 1

If preorder or postorder is given then construction of BST will take O(nlogn) 

• Preorder is given and we know that inorder is sorted .
• We get inorder in O(nlogn) time ( apply merge sort) 
• With the help of inorder and preorder we can construct BST in O(n) time.
• Overall complexity= n + nlogn = o (nlogn) 

Answer 2

1-as here binary search tree is given so we can construct binary search tree  using either preorder or postorder in O(n) time using efficient algorithm or method like stack method.

2-if we use sorting algo and with the help of sorting algo we can find inorder traversal of binary search tree in O(nlogn) and with the help of inorder and preorder or inorder and postorder we can contruct binary search tree in O(nlogn) (using binary search)

so total time taken=O(nlogn)+O(nlogn)=O(nlogn) (in this case time complexity is not efficient)

3-yes we can construct unique binary search tree only using preorder or postorder unsing efficient method like stack method.

4-in case of binary tree ( not binary search tree) we need to have inorder and preorder or inorder and postorder to construct unique binary tree ,in that case time complexity=O(nlogn)

https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

https://www.geeksforgeeks.org/construct-a-binary-search-tree-from-given-postorder/