Question

For an integer n≥1 let T(n) be the “line” tree where 1 is the root, 2 is the right child of 1, 3 is the right child of 2, and so on until n which is the right child of n−1. For each of the following trees, give the sequence rotations that make the depth of the trees minimal:T(3), T(5), T(6), T(7). For each rotation say if it is left or right, and the node at which it is applied.

Answer 1

For T(3):

Perform one left rotation on node 2

Now height will be minimum which is 1.

For T(5):

Perform one left rotation on node 3

Now height will be minimum which is 2

For T(6):

Perform one left rotation on node 3

Then perform one left rotation on node 5

Now height will be minimum which is 2

For T(7)

Perform one left rotation on node 4

Then perform one right rotation on node 2

Then perform one left rotation on node 6

Now height will be minimum which is 2