**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))?

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
- Pick the smaller head and advance its pointer
- 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[1]
- 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))

[1] 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}
```

Licensed under: CC-BY-SA with attribution

Not affiliated with: Stack Overflow