CareerCup

I the question its written binary tree but all are discussing about BST , can any one clear it .. is that BST or Binary Tree.

if they are binary trees than add at any leaves. In case of BST than the complexity would be mlogn or nlogm .

1) Perform In-order traversal on the smaller tree, let's say the tree of size m (m<n). Store the now sorted keys => Complexity = mlog(m)

2) Insert the m (unnecessarily sorted) keys into tree n => Complexity = (m+n) log (m+n).

Complexity of 2 steps is the sum.

(?)

we should convert the binary trees to lists and finally merge.

can anyone give an example of merging, i am not able to underestand what merging is

node *mergebst (node *root1, node *root2)
{
stack s1;
stack s2;

while (!root1)
{
s1.push(root1);
root1= root1->left;
}

while (!root2)
{
s2.push(root2);
root2= root2->left;
}

int m= no of element in bst1
int n= no of ellements in bst2
return mbst( &s1, &s2, (m+n);
}

node * mbst( stack *s1, stack *s2, n)
{
node *ret = NULL;
if (n<=0)
return NULL;

lc = mbst (s1, s2, n/2);

node * p1 = s1->top()
node * p2 = s2->top()

if ((p1->data <= p2->data) || p2 == underflow)
{
p1 = s1->pop();
ret = p1;
p1 = p1->right();
while (!p1)
{
s1->push(p1)
p1=p1->left;
}
}
else { ..do the same for p2..}

rc = mbst (s1,s2, n-n/2-1);
ret ->left = lc;
ret->right = rc;
return ret;
}

Algo :

1. Convert the two binary trees to DLLs
2. Merge Two DLLs
3 Convert merged DLL to Binary tree.

Overall Worst Case : O(m+n)

if we have two trees of length m and n, say m < n,
everytime we remove one element from m tree and insert inton n tree.
the complexity of each insertion will be log(n+i), i will be extra addition to tree.
total complexity should be
log(n) + log(n+1) +...+ log(n+m)
= log(n * (n+1)*..*(n+m)) = log((n+m)!) - log((n-1)!)

Start from the root of say BST1, and search for its correct position in other tree BST2. Let this be node x, now if root of BST1 lies to the right of x, then attach the root as well as whole right sub-tree at this node, and perform the same operation with left sub tree as BST1.
Thus, we will do a search (O(lg n)) in BST2 O(lg m) time which is the height of BST1.
Hence complexity is O(lg m . lg n).