### Merging two binary trees

You are given two height balanced binary search trees

*T*and*T'*, storing*m*and*n*elements respectively. Every element of tree*T*is smaller than every element of tree*T'*. Every node*u*also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time*O(*log*m*+ log*n)*(preserving both the height balance and the order)?
we can do this by making root of T the left child of left most element of T' and then successively doing right rotation by taking root of T' as pivot until whole tree is balanced.

ReplyDelete