2016-05-25-left-rotate-a-binary-tree-in-javascript

2016-05-25-left-rotate-a-binary-tree-in-javascript.md

Title: Left Rotate a Binay Tree in Javascript

Author: Mikael Lundin

Date: 2016-05-25

URL: http://blog.mikaellundin.name/2016/05/25/left-rotate-a-binary-tree-in-javascript.html

complete.js

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);
};

expression.js

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

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

expressionTree.js

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

leftRotate.js

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;
};