Binary Tree Node Insertion

Question

I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript.

I was thinking especially about the node insertion method. Here's my implementation:

class BinaryTree {
// ... initialization
add(val) {
    if(this.root === null) {
        this.root = new Node(val);
        return ;
    }
    this.addNode(val, this.root);
}
addNode(val, node) {
    if(!!!this.comparator) throw new Error('this.comparator cannot be undefined.');
    let comp = this.comparator(val, node.val);
    if(comp === -1) {
        if(node.left === null) {
            node.left = new Node(val);
            return ;
        }
        this.addNode(val, node.left);
    }
    else if(comp === 1) {
        if(node.right === null) {
            node.right = new Node(val);
            return ;
        }
        this.addNode(val, node.right);
    }
}
// ... other methods
}

where this.comparator = (v1, v2) => { return (v1 <= v2) ? -1 : 1; };

My questions are:

• Is there a way to modify this add method such that it can balance the tree after every addition?
• If so, by factor would the time complexity of add be growing?

Answer 1

Search & read on AVL trees that follow the BST rules while keeping a worstcase balance difference of 1 between subtrees. read knuth sorting & searching