Prove maximum number of rotations for two trees to become equal

Question

In the book Introduction To Algorithms - A Creative Approach, Question 4.24:

Let T1, and T2 be two arbitrary trees, each having n nodes. Prove that it is sufficient to apply at most 2n rotations to T1, so that it becomes equal to T2.

For binary search trees, I figured out an algorithm:

1. Find the element which is equal to T2's root, let's call it target-root.

2. Using AVL rotation strategy, rotate target-root to make it T1's new root.
   During this process, multiple rotations may be performed.

3. For the left sub tree of T1 and T2, process them as above recursively.
   For the right sub tree of T1 and T2, process them as above recursively.

This algorithm, when in worst-case, runs in O(N^2).

I don't quite understand the phrase “arbitrary trees”, and I can't figure out how to make T1 equal to T2.

Could anyone help on this question?

Answer 1

From whatever i have got i can propose an algorithm that can solve this problem in O(N) rotations but could not get the exact upper bound but think you can build on this:-

Here is pseudo code for algorithm:-

 //Method to make T1 equivalent to T2

    alignTree(T1,T2) {

     if(length(T1)==1)
        return

     else {

        Node k = FindRoot(T1,T2)
        rotateAbout(k)
        align(T1.left,T2.left)
        align(T1.right,T2.right)
     }


    }

Suppose FindRoot finds the node of T1 which is considered to be root of new Tree which is equivalent tree. Suppose rotateAbout(K) makes appropriate rotation to root to get equivalent nodes on left and right subtrees of new tree. Then we can recursively solve for smaller sub-problems on smaller subtrees.

No of Rotations: As you can see in pseudo code the no of rotation is equivalent to pre-order traversal of tree which is O(N)

Note: You can always extend the above pseudo code for general tree and still get same complexity.