how to merge two BST's efficiently?

Question

how to merge two binary search trees maintaining the prop of BST...naive way of doing it is

take each element from a tree and insert it into the other...

Complexity of this method being O(n1 * log(n2))..

where n1 is the no 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 T2 is the only BST that has n1+n2 nodes...

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

thanks in advance..

Answer 1

What about flattening both trees into sorted lists, merging the lists and then creating a new tree?

Answer 2

• Flatten trees into sorted lists.
• Merge sorted lists.
• Create tree out of merged list.

IIRC, that is O(n1+n2).

Answer 3

If I was permitted to comment, I would. Given this answer:

• Flatten trees into sorted lists.
• Merge sorted lists.
• Create tree out of merged list.

The run-time is O((n1 + n2) + (n1 + n2)log(n1 + n2)) because you still need to build the tree even after you have a merged list, or if you use a common sorting method to sort the lists as suggested, you have a O((n1log(n1)) + n2(logn2)) expense, which factors to the same value.

Please explain to me so I understand how my calculations are wrong. Thank you.

Answer 4

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)
  • The value at the middle would be the root, and recurse.
  • 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))

Answer 5

ya i agree with the above solution

Answer 6

how about just finding correct position for the root node of the second tree and just "attaching" the root node there?

Answer 7

Jonathan,

After sorting, we have a list of length n1+n2. Building a binary tree out of it will take log(n1+n2) time. This is same as merge sort, only that at each recursive step we wont have a O(n1+n2) term as we have in merge sort algorithm . So the time complexity is log(n1+n2).

Now the complexity of the whole problem is O(n1+n2).

Also I would say this approach is good if two lists are comparable size. If the sizes are not comparable then it is best to insert every node of the small tree into a large tree. This would take O(n1*log(n2)) time. For example if we have two trees one of size 10 and another of size 1024. Here n1+n2 = 1034 where as n1log(n2) = 10*10 = 100. So approach has to depend upon the sizes of the two trees.

Answer 8

O(n1 * log(n2)) is the average case scenario even if we have 2 merge any unsorted list into a BST. We are not utilizing the fact that list is sorted list or a BST.

According to me Lets assume one BST has n1 elements and other has n2 elements. Now convert one BST into a Sorted Array List L1 in O(n1).

Merged BST(BST, Array)

if (Array.size == 0) return BST if(Array.size ==1) insert the element in the BST. return BST;

Find the index in the array whose left element < BST.rootnode and right element >=BST.rootnode say Index. if(BST.rootNode.leftNode ==null ) //i.e No left node { insert all the array from Index to 0 into left of BST and } else { Merged BST(BST.leftNode, Array{0 to Index}) }

if(BST.rootNode.rightNode ==null)//i.e No right node { insert all the array from Index to Array.size into right of BST } else { Merged BST(BST.rightNode, Array{Index to Array.size}) }

return BST.

This algorithm will take << time than O(n1 * log(n2)) as every time we are partitioning the array and BST to handle the subproblem.

---