2 votes 2 votes What is the worst case time complexity to construct unique BST from a:) Inorder and preorder a:) Inorder and postorder Programming in C data-structures tree binary-search-tree + – rahul sharma 5 asked Oct 2, 2017 rahul sharma 5 467 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply saxena0612 commented Oct 2, 2017 reply Follow Share I think it will be O(n2), Think about this case Here Preorder : ABC Whereas In order : CBA You will select the first element from preorder sequecne because it will be root anyways.And increment. You traverse Inorder sequence to find partition and end up traversing complete elements and there is no such partition exist. The second step again chooses the second element from B and end up finding that there is no partition thus for every element you are traversing the second sequence. 0 votes 0 votes joshi_nitish commented Oct 2, 2017 reply Follow Share why you are not using binary search while searching in inorder?? 0 votes 0 votes Shubhanshu commented Oct 2, 2017 reply Follow Share O(nlogn) in both the above mentioned cases. 0 votes 0 votes rahul sharma 5 commented Oct 2, 2017 reply Follow Share Here :- http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/ Method 2,they have given 0(n) method. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes It is $\Theta (nlogn)$ s_dr_13 answered Mar 10, 2019 s_dr_13 comment Share Follow See 1 comment See all 1 1 comment reply abhishekmehta4u commented Mar 10, 2019 reply Follow Share How , Can u explain ?? 0 votes 0 votes Please log in or register to add a comment.
