I am trying to write a method for a binary search tree class to modify a balanced a normal tree which makes the tree have nodes only on one side.
From the order in which the elements are appearing in the unbalanced tree, to me there seems to be some relation between the In Order Traversal (Left, Middle, Right).
void unbalance(Node **pp) {
Node *p;
while ((p = *pp)) {
if (!p->left) {
pp = &p->right;
} else {
Node *tmp = p->left->right;
*pp = p->left;
p->left->right = p;
p->left = tmp;
}
}
}
...
Node *tree = ...;
unbalance(&tree);
This code is based on @templatetypedef's answer. It uses a pointer-to-pointer to avoid orphaning nodes (which also gets rid of finalRoot, whose only purpose is to avoid orphaning the original root passed in by the caller).
The idea is to walk down the tree along the rightmost branch. If there never are any left children, we only enter the first part of the if statement and exit without doing anything.
The else part is used when there is a left subtree. In that case we rotate the tree right. 
This has the effect of pulling one node up from the left subtree, i.e. our left subtree is now one node smaller. We repeat this until the left subtree is completely gone, at which point we enter the first part of the if again. Then we go down to the remaining right subtree and repeat the whole thing.
Pointer-to-pointers are often useful when modifying the structure of a linked list or tree. They let us work directly on the original pointers instead of making a copy of them. In this case, the assignment *pp = ... modifies a pointer elsewhere (the one pp is pointing to). This is either the original root (as passed in by the caller), or one of the right pointers within the tree (as set by pp = &p->right). This repointing is needed because the tree rotation in the else branch shuffles nodes around, so what used to be the root of a subtree gets moved further down, and the former left node gets pulled up to become the new root. We update *pp to preserve the invariant that the pointer higher up (either the tree variable in our caller or the right member of our parent node) points to the (new) root of the subtree.
One way to do this iteratively is to use tree rotations. The idea goes something like this:
In pseudocode:
Node finalRoot = null;
while (currNode != null) {
if (currNode.left != null) {
currNode = rotateRight(currNode);
} else {
if (finalRoot == null) finalRoot = currNode;
currNode = currNode.right;
}
}
return finalRoot;
This approach is adapted from the Day-Stout-Warren algorithm, which does this as its first step. It runs in time O(n).
if (finalRoot == null) part: It's inelegant. And now I know why: It's treating the original root pointer (initial value of currNode) differently from all the other pointers currNode steps through (all the .right children). I think this means the pseudocode is broken: It doesn't update currNode.right, so the tree loses access to all the left nodes that were rotated in.
finalRoot is not actually the initial tree root - it ends up being the rightmost node in the tree (trace through the code on a sample tree). Also, can you elaborate on the bit about losing nodes? When we descend into the right subtree we know there is no left subtree to lose (and that everything above us is in a giant spine.)
A.right never gets updated and so keeps pointing to B, even when B is no longer the root of its subtree.