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– User2015年11月04日 09:50:03 +00:00Commented 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– user1232015年11月04日 10:34:09 +00:00Commented 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– dagnelies2015年11月04日 12:25:37 +00:00Commented Nov 4, 2015 at 12:25
-
2Take a look at How to merge two BST's efficiently?manlio– manlio2015年11月04日 13:29:08 +00:00Commented Nov 4, 2015 at 13:29
1 Answer 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.
lang-cpp