data structure

Question

two (possibly unbalanced) BST's containing n elements each can be merged into a single BST in O(n) time - TRUE

if it was balanced then it would be O(log n) right?

Comments

2 bst cannot merged in single bst in o(log(n))  whether both bst is balanced or not in worst case

Answer 1

in both the cases complexity would be O(n)....

procedure:- find inorder (O(n)) traversal of both tree and merge them :-(2O(n) for inorder+O(2n-1)for merging...

therefor O(n) 

Note:-point to be noticed ..in case  of BST Inorder traversal will be in ascending order (sorted array)

Comments

@A_i_$_h @hs_yadav

once you have found sorted sequence, you can find BST from that sequence using divide and conquer, it will take O(n) time.

---

@joshi

here it does not said that elements are sorted....only a set of n elements are given...even if you are going to sort the elements{O(nlogn)} then ,i think, question would be modified....???

question asked by @ A_i_$_h

To construct a BST from n elements?

time complexity?

---

@hs_yadav

see my comment, what i have written

"once you have found sorted sequence, you can find BST from that sequence using divide and conquer, it will take O(n) time."