I'm learning basic algorithms for the hell of it, and I am hoping you guys could help me. I'll be using recursion.
So I am wanting to balance an ordered, fully right-balanced tree where for every node n, n.right = n.d+1 (from 1 to 15). I have 15 nodes.
I have two methods that I think I should use. Rotate left and rotate right. Both work as intended. I also know that because I have 15 nodes, the number of levels I need is ceiling(log2(15)), so in this case four.
The trouble I'm having is if I have an odd number of nodes, I need to, in this case since the heightRight(root) > heightLeft(root), rotate left until the heights are equal. Then here is my problem with the recursive procedure. Passing (n.left), then n.right (where the base n would be the root. The case would be different with an even number of nodes (then the height difference from the left of root and right of root can differ by at most 1.)
I'm not sure if I am accurately describing my problem or not.