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