Rotation distance between two binary trees

327 Views Asked by At

I have the following binary tree, which I'm trying to convert into the target binary tree (second tree in the post) using minimum number of tree rotations. The theoretical minimum number of rotations for this tree is 5, however, the smallest value I can figure out is 6 rotations, I have copied the rotations as well, what am I missing?

Tree: 1 \ \ 3 / \ / \ 2 5 / \ / \ 4 7 / \ / \ 6 11 / \ / \ 9 12 / \ 8 10

Target Tree: 1 \ \ 11 / \ / \ 9 12 / \ / \ 3 10 / \ / \ 2 5 / \ / \ 4 7 / \ 6 8

The rotations I have tried so far (all of which require 6 rotations):

Order1: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 3 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9 Order2: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9

Order3: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 3 and pivot 9

Order4: Rotate left with root 7 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 11 Rotate left with root 3 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9

Order5: Rotate left with root 7 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 3 and pivot 9

1

There are 1 best solutions below

0
On BEST ANSWER

Rotate right with root 11 and pivot 9
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 9
Rotate left with root 9 and pivot 11