# How to merge two BST's efficiently?

### Question

How to merge two binary search trees maintaining the property of BST?

If we decide to take each element from a tree and insert it into the other, the complexity of this method would be `O(n1 * log(n2))`, where `n1` is the number of nodes of the tree (say `T1`), which we have splitted, and `n2` is the number of nodes of the other tree (say `T2`). After this operation only one BST has `n1 + n2` nodes.

My question is: can we do any better than O(n1 * log(n2))?

1
25
10/19/2015 7:13:16 PM

Naaff's answer with a little more details:

• Flattening a BST into a sorted list is O(N)
• It's just "in-order" iteration on the whole tree.
• Doing it for both is O(n1+n2)
• Merging two sorted lists is into one sorted list is O(n1+n2).
• Keep pointers to the heads of both lists
• This is how the merge of merge-sort works
• Creating a perfectly balanced BST from a sorted list is O(N)
• See code snippet below for algorithm
• In our case the sorted list is of size n1+n2. so O(n1+n2)
• The resulting tree would be the conceptual BST of binary searching the list

Three steps of O(n1+n2) result in O(n1+n2)

For n1 and n2 of the same order of magnitude, that's better than O(n1 * log(n2))

 Algorithm for creating a balanced BST from a sorted list (in Python):

``````def create_balanced_search_tree(iterator, n):
if n == 0:
return None
n_left = n//2
n_right = n - 1 - n_left
left = create_balanced_search_tree(iterator, n_left)
node = iterator.next()
right = create_balanced_search_tree(iterator, n_right)
return {'left': left, 'node': node, 'right': right}
``````
26
7/1/2018 7:59:59 AM