Converting One Binary Tree into another with tree rotation

Question

Given are two random binary trees. I need to find a sequence of rotations, so that tree one equals tree two after i am done with them.

For instance:

• Tree one has 0 as root, 1 as a left and 2 as a right child
• Tree two has 1 as root, its right child is 0, zeros right child is 2
• Output: Rotate right around node 0.

How do I do that for random binary trees?

Answer 1

It's impossible to do this for random binary trees.

For example, consider these two trees: Tree 1 has 0 as its root, 1 as 0's right child; Tree 2 has 1 as its root, 0 as 1's right child. It's obvious that we can not turn tree 1 to tree 2 by rotation.

But it's possible to do this for random binary search trees(as larger elements will be on the right of smaller elements). We can find the root of tree 2 in tree 1, and rotate it to the root. Then we just go into its left and right subtrees to solve them recursively.

EDIT

If it's guaranteed that the answer always exist, then we can consider them as binary search trees(as rotation will keep the properties of binary search trees). Actually, we can relabel the nodes of the two trees to change them into binary search trees, but it's not a must for solving this problem.

Now we can change Tree #1 into Tree #2 recursively using the following algorithm.

procedure solve(tree1: the first tree, tree2: the second tree)
    return if either tree1 or tree2 is empty
    r := root of tree2
    find r in tree1 and rotate r to the root
    solve(left subtree of the root of tree1, left subtree of the root of tree2)
    solve(right subtree of the root of tree1, right subtree of the root of tree2)