With only these 2 constraints you can just insert the root of smaller tree into bigger one and using rotations bring it to leaf. Now attach the left and right subtrees to the inserted node. Expected O(log n) Worst O(n) Space O(1)
-Rohit On Mon, Mar 8, 2010 at 5:14 AM, lalit gera <[email protected]> wrote: > new tree will be a right skewed tree...... any other idea?? > > On Jan 29, 6:55 am, ShingRay <[email protected]> wrote: > > Oh, I have said something wrong. > > 1. Inorder traverse both trees. This gives two sorted list. È(m+n) > > 2. Merge the two sorted list A, B into a new one C. È(m+n) > > 3. Build a new tree using C. Each node of the tree has just one child. > > È(m+n) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
