0

What time in terms of Big O will it take to merge two BST's in One? Each having no of nodes n and height O(log n) with no common element.

Resultant should be also a BST

4
  • What is the algorithm?
    – User
    Nov 4, 2015 at 9:50
  • There isn't any algorithm given its a general question. But I guess it is done by Search function of BST and Insert.
    – user123
    Nov 4, 2015 at 10:34
  • The naive way would be to iterate the smaller tree (n) and insert each node into the bigger one (m). Resulting in O(n*log(m+n)) ...perhaps there is a fancy algortihm which can do that it a "hand in hand" iteration and result in O(n+m) ...at least that would be the lowest attainable bound. Whether there is an algo achieving it is another question.
    – dagnelies
    Nov 4, 2015 at 12:25
  • 2
    Take a look at How to merge two BST's efficiently?
    – manlio
    Nov 4, 2015 at 13:29

1 Answer 1

1

The StackOverflow post @manlio pointed out is an exact duplicate. Basically, yes, the algorithm can improved to O(n+m); the approach is to flatten the trees to sorted lists, merge them, and recreate a BST. This page also has some example code that may be of interest as well.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.