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

  • What is the algorithm? – User Nov 4 '15 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 '15 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 '15 at 12:25
  • 2
    Take a look at How to merge two BST's efficiently? – manlio Nov 4 '15 at 13:29

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.