Binary Search Tree - Balancing (Day-Stout-Warren)

JavaScript

'use strict';

// Balancing an unordered BST using Day-Stout-Warren algorithm
//	https://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm

const assert = function (expr, msg) {
    if (!expr) {
        throw new Error(msg);
    }
};

class Node {
    constructor(data) {
        this.key = data;
        this.left = null;
        this.right = null;
    }
}

class BSTNode extends Node {

    constructor(data) {
        super(data);
    }

    add(data) {
        assert(this.key !== data, "data should not exist in the tree already: " + data);
        if (data < this.key) {
            if (this.left == null) {
                this.left = new BSTNode(data);
                return;
            } else {
                this.left.add(data);
            }
        } else if (data > this.key) {
            if (this.right == null) {
                this.right = new BSTNode(data);
                return;
            } else {
                this.right.add(data);
            }
        }
    }
}

class Tree {
    constructor(rootNode) {
        assert(rootNode instanceof BSTNode, "rootNode must be of type 'BSTNode'");
        this.root = rootNode;
        this.nodeCount = 1;
    }

    insert(data) {
        if (data instanceof Array) {
            data.forEach(d => this.root.add(d));
            this.nodeCount += data.length;
        } else {
            this.root.add(data);
            this.nodeCount++;
        }
    }

    traverse(processCallback) {
        function inOrder(node) {
            if (node) {

                if (node.left != null) {
                    inOrder(node.left);
                }

                processCallback.call(this, node);

                if (node.right != null) {
                    inOrder(node.right);
                }

            }
        }
        inOrder(this.root);
    }

    balance() {
        function treeToVine(root) {
            let tail = root;
            let rest = tail.right;
            while (rest != null)...