self doubt

Question

what is the time complexity to construct binary search tree when preorder and postorder of tree given?

answer given is O(n)

but i think it will be nlogn...becz from given postorder or preorder we need to find in order by sortingin nlogn tum so I think overalltime complexity will be nlogn ..???

Comments

yes,O(n) is correct!

---

@Shaik Masthan ..if the question was to construct unique binary tree with either or both pre and post order given, then it won't be possible...as inorder is required.. am i correct...pls reply?

---

correct, binary tree cant be constructed without inoder

but bst can be constructed

Answer 1

let me answer this question if preorder or postorder traversal of binary search tree is given  then we can find inorder traversal by sorting the elements in ascending order using efficient sorting algorithm in O(nlogn) time and with the help of inorder and postorder or inorder and preorder we can construct BST in O(nlogn) time ,

so total time complexity =O(nlogn)+O(nlogn)=O(nlogn)

But why to find inorder traversal to construct BST if preorder or postorder is given?

we can construct BST with  preorder or postorder only using efficient algorithm like stack method in O(n) time.

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

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

Comments

thanks for sharing link