If the trees are not ordered or balanced, you can do this in O(n) time. Just walk the nodes of Tree A until you find one with a child missing and attach Tree B at that location. Some people are confused by the fact that each individual step of a tree walk can take up to O(log n) time. But for the whole tree, the costs amortize nicely so that the total cost of the walk is O(n), not O(n log n).
If the trees _are_ ordered and/or balanced, then the solution you proposed (deconstructing both trees and building a new one) still takes only O(n log n) time. You don't need the extra log(n) time. Now if you meant n log(log(n)), that's harder. On Jul 26, 7:46 am, Manjunath Manohar <[email protected]> wrote: > no just a BT, the tree can be in any form..it need not be balanced also.. -- 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.
