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)?


  1. 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.


Post a Comment

Popular posts from this blog