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.