How would I balance a degenerate tree? C++ Data Structure

Question

I am currently learning data structure using C++. I understand how you would balance binary search tree as you insert new nodes.

However, what if you already have a degenerate tree(single linklist), and want to balance that without creating a new tree? In conclusion, how would I reassemble the degenerate tree to a complete tree using existing nodes? (USING ROTATION methods)

For example, my nodes hold data of(9 nodes): 1, 3 , 6, 9, 12, 15, 18, 21, 24

I need a push off start for this. Im not sure where to even begin.. I appreciate your help.

Answer 1

A degenerate tree is just a sorted linked list. Find the middle element of the list, remove the beginning of the list before the middle and attach it to the left of the middle element. Now you have the middle element as the root and two degenerate trees (linked lists) on each side. Repeat this procedure recursively for each side.