This is homework. I'm simply looking for a helpful suggestion to nudge me.

I have to show that any binary search tree with n nodes can be restructured into any other n node tree in O(n) rotations.

So here's what I've done:

Tree A. (disregard the values....they are just for me to distinguish them)

1

/ \

2 3

/ \ / \

4 5 6 7

Tree B.

7

/ \

6 5

/ \ / \

4 3 2 1

These will be my test trees. I want to make A look like B (re-order the nodes properly)

So, my thought is to make A a left chain.

Note: I've put x's where some null nodes are located.

step 1. (every step is a single left rotation)

3

/ \

1 7

/ \ / \

2 6 x x

/ \

4 5

step 2.

7

/ \

3 x

/ \

1 x

/ \

2 6

/ \

4 5

step 3.

7

/ \

3 x

/ \

6 x

/ \

1 x

/ \

2 x

/ \

4 5

step 4.

7

/ \

3 x

/ \

6 x

/ \

1 x

/ \

5 x

/ \

2 x

/ \

4 x

K.

Now, I do the same thing for Tree B. All left rotations, and I end up with:

1

/ \

5 x

/ \

2 x

/ \

7 x

/ \

3 x

/ \

6 x

/ \

4 x

Now, I think I need to use the rotations in some type of reverse order of tree B's movement to a left chain to restructure A to look like B in the beginning.

Can someone offer a tip? Many thanks.

If so, then your example with B is wrong.