Left Rotate a Binary Tree in javascript

How did I end up here? I ask myself. I'm sitting in my couch in front of the TV, but it's not turned on. The clock is way past bedtime and I'm scribbling binary trees, transforming them, while drinking coffee.

It started with implementing a toy compiler on my spare time. I managed to parse a set of expressions that would add integers together.

1 + 2 + 3 + 4 + 5

Addition is as simple as it gets, because a + b = b + a. I knew it was generating an expression tree, but I didn't really care what it looked like.

And this evening I thought I should just add subtraction to mix it up.

1 - 2 + 3 - 4 + 5

The implementation was easy enough and the result was 5. Now, wait a minute. That doesn't seem right. The result should be 3 right? Suddenly I needed to start caring about that expression tree.

The reason for it to evaluate to 5 would be that the expression tree looks like this.

1 - (2 + (3 - (4 + 5))) = 5

This is not how you do this calculation. Instead you should calculate it from left to right, like this.

(((1 - 2) + 3) - 4) + 5 = 3

Going back to the expression tree we would need something that looks like this.

In order to accomplish this you can do something called left rotation of the binary tree and there is an excellent article on Wikipedia on how to do this. The following image describes this very well.

This is easy enough when you have a complete tree that you want to rotate, the problem is that my tree was built from bottom up. This is very common, so I needed a way of rotating the tree while building it.

Let's first take a look at how the tree is built.

If we're to visualize this in javascript it would look like this.

new Expression('-',
    new Value(1),
    new Expression('+',
        new Value(2),
        new Expression('-',
            new Value(3),
            new Expression('+',
                new Value(4),
                new Value(5))
            )
        )
    );

What I would like to do in the Expression constructor, is to rotate the tree to the left. This is not that hard to do if you think of it.

Doing this in javascript is surprisingly easy.

function leftRotate(node) {
    var rightNode = node.right;

// right is a node and not a leaf
if (rightNode.nodeType === 'node') {
    node.right = rightNode.left;
    rightNode.left = node;
    return leftRotate(rightNode);
}

return rightNode;

};

For every node that is added, it needs to be left rotated until there is no more right nodes to rotate with.

This function works very well when working the tree from outside the Expression, but what I try to do, is to rotate the tree in the constructor as the tree is being created.

var Expression = function(content, left, right) {
    this.content = content;
    this.left = left;
    this.right = right;

// ERROR: this is not assignable
this = leftRotate(this);

};

Since the constructor cannot assign this, there is no way to do this as clean as before. We need to rewrite leftRotate so it copy the references and content instead of moving the entire node down the tree.

function leftRotate(node) {
    var rightNode = node.right;

// right is a node and not a leaf
if (rightNode.nodeType === 'node') {
    // copy node content
    var content = node.content;
    node.content = rightNode.content;
    rightNode.content = content;

    // left rotation
    node.right = rightNode.right;
    rightNode.right = rightNode.left;
    rightNode.left = node.left;
    node.left = rightNode;

    leftRotate(rightNode);
}

};

var Expression = function(content, left, right) {
    this.content = content;
    this.left = left;
    this.right = right;
// left rotate this node down the tree
leftRotate(this);

};

This is not as pure as the first solution, but this actually works inside the Expression constructor by simply mutating the binary tree in a left rotation.