binary-search-tree.js

// implementation of binary search tree

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

class BinarySearchTree {
    constructor() {
      this.root = null;
    }
  
    add(data) {
      const node = new Node(data);
      if(!this.root) {
        this.root = node;
      } else {
        let current = this.root;
        while(current) {
          if(node.data < current.data) {
            if(!current.left) {
              current.left = node;
              break;
            }
            current = current.left;
          } else if (node.data > current.data) {
            if(!current.right) {
              current.right = node;
              break;
            }
            current = current.right;
          } else {
            break;
          }
        }
      }
    }

    remove(data){
        const that = this;
        const removeNode = function(node, data){
            if(!node){
                return null;
            }
            if(data === node.data){
                if(!node.left && !node.right){
                    return null;
                }
                if(!node.left){
                    return node.right;
                }
                if(!node.right){
                    return node.left;
                }

                //2 children
                const remp = this.getMin(node.right);
                node.data = temp;
                node.right = removeNode(node.right, temp);
                    return node;
                } else if(data < node.data){
                    node.left = removeNode(node.left, data);
                    return node;
                } else {
                    node.right = removeNode(node.right, data);
                    return node;
                }
        };
        this.root = removeNode(this.root, data);
    }

    contains(data){
        let current = this.root;
        while(current){
            if(data === current.data){
                return true;
            }
            if(data < current.data){
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }

    _preOrder(node, fn){
        if(node){
            if(fn){
                fn(node);
            }
            this._preOrder(node.left, fn);
            this._preOrder(node.right, fn);
        }
    }

    _inOrder(node, fn){
        if(node){
            this._inOrder(node.left, fn);
            if(fn){
                fn(node);
            }
            this._inOrder(node.right, fn);
        }
    }

    _postOrder(node, fn){
        if(node){
            this._postOrder(node.left, fn);
            this._postOrder(node.right, fn);
            if(fn){
                fn(node);
            }
        }
    }

    traverseDFS(fn, method){
        const current = this.root;
        if(method){
            this[`_${method}`](current, fn);
        } else {
            this._preOrder(current, fn);
        }
    }

    traverseBFS(fn){
        this.queue = [];
        this.queue.push(this.root);
        while(this.queue.length){
            const node = this.queue.shift();
            if(fn){
                fn(node);
            }
            if(node.left){
                this.queue.push(node.left);
            }
            if(node.right){
                this.queue.push(node.right);
            }
        }
    }

    print() {
        if(!this.root) {
          return console.log('No root node found');
        }
        const newline = new Node('|');
        const queue = [this.root, newline];
        let string = '';
        while(queue.length) {
          const node = queue.shift();
          string += `${node.data.toString()} `;
          if(node === newline && queue.length) {
            queue.push(newline);
          }
          if(node.left) {
            queue.push(node.left);
          }
          if(node.right) {
            queue.push(node.right);
          }
        }
        console.log(string.slice(0, -2).trim());
      }
    

    printByLevel(){
        if(!this.root){
            return console.log('No root node found');
        }
        const newline =new Node ('\n');
        const queue = [this.root, newline];
        let string = '';
        while(queue.length){
            const node = queue.shift();
            string += node.data.toString() + (node.data !== '\n' ? ' ' : '');
            if(node === newline && queue.length){
                queue.push(newline);
            }
            if(node.left){
                queue.push(node.left);
            }
            if(node.right){
                queue.push(node.right);
            }
        }
        console.log(string.trim());
    }

    getMin(node){
        if(!node){
            node = this.root;
        }
        while(node.left){
            node = node.left;
        }
        return node.data;
    }

    getMax(node){
        if(!node){
            node = this.root;
        }
        while(node.right){
            node = node.right;
        }
        return node.data;
    }

    _getHeight(node){
        if(!node){
            return -1;
        }
        const left = this._getHeight(node.left);
        const right = this._getHeight(node.right);
        return Math.max(left, right) + 1;
    }

    getHeight(node){
        if(!node){
            node = this.root;
        }
        return this._getHeight(node);
    }

    _isBalanced(node){
        if(!node){
            return true;
        }
        const heightLeft = this._getHeight(node.left);
        const heightRight = this.getHeight(node.right);
        const diff = Math.abs(heightLeft - heightRight);
        if(diff > 1){
            return false;
        } else {
            return this._isBalanced(node.left) && this._isBalanced(node.right);
        }
    }

    isBalanced(node){
        if(!node){
            node = this.root;
        }
        return this._isBalanced(node);
    }

    _checkHeight(node){
        if(!node){
            return 0;
        }
        const left = this._checkHeight(node.left);
        if(left === -1){
            return -1;
        }
        const right = this._checkHeight(node.right);
        if(right === -1){
            return -1;
        }
        const diff = Math.abs(left - right);
        if(diff > 1){
            return -1;
        } else {
            return Math.max(left, right) + 1;
        }
    }

    isBalancedOptimized(node){
        if(!node){
            node = this.root;
        }
        if(!node){
            return true;
        }
        if(this._checkHeight(node) === -1){
            return false;
        } else {
            return true;
        }
    }
}  

const binarySearchTree = new BinarySearchTree();
binarySearchTree.add(5);
binarySearchTree.add(3);
binarySearchTree.add(7);
binarySearchTree.add(2);
binarySearchTree.add(4);
binarySearchTree.add(6);
binarySearchTree.add(8);
binarySearchTree.print();
binarySearchTree.printByLevel();
console.log('--DFS inOrder');
binarySearchTree.traverseDFS(node =>{ console.log(node.data); }, 'inOrder');
console.log('---DFS postOrder');
binarySearchTree.traverseDFS(node => { console.log(node.data); }, 'preOrder');
console.log('--- DFS postOrder');
binarySearchTree.traverseDFS(node => { console.log(node.data); }, 'postOrder');
console.log('---BFS');
binarySearchTree.traverseBFS(node => { console.log(node.data); });
console.log('min is 2:', binarySearchTree.getMin());
console.log('max is 8:', binarySearchTree.getMax());
console.log('tree contains 3 is true:', binarySearchTree.contains(3)); // => true
console.log('tree contains 9 is false:', binarySearchTree.contains(9)); // => false
console.log('tree height is 2:', binarySearchTree.getHeight()); // => 2
console.log('tree is balanced is true:', binarySearchTree.isBalanced()); // => true
binarySearchTree.remove(11); // remove non existing node
binarySearchTree.print(); // => 5 | 3 7 | 2 4 6 8
binarySearchTree.remove(5); // remove 5, 6 goes up
binarySearchTree.print(); // => 6 | 3 7 | 2 4 8
binarySearchTree.remove(7); // remove 7, 8 goes up
binarySearchTree.print(); // => 6 | 3 8 | 2 4
binarySearchTree.remove(8); // remove 8, the tree becomes unbalanced
binarySearchTree.print(); // => 6 | 3 | 2 4
console.log('tree is balanced is false:', binarySearchTree.isBalanced()); // => true
binarySearchTree.remove(4);
binarySearchTree.remove(2);
binarySearchTree.remove(3);
binarySearchTree.remove(6);
binarySearchTree.print(); // => 'No root node found'
binarySearchTree.printByLevel(); // => 'No root node found'
console.log('tree height is -1:', binarySearchTree.getHeight()); // => -1
console.log('tree is balanced is true:', binarySearchTree.isBalanced()); // => true
console.log('---');
binarySearchTree.add(10);
console.log('tree height is 0:', binarySearchTree.getHeight()); // => 0
console.log('tree is balanced is true:', binarySearchTree.isBalanced()); // => true
binarySearchTree.add(6);
binarySearchTree.add(14);
binarySearchTree.add(4);
binarySearchTree.add(8);
binarySearchTree.add(12);
binarySearchTree.add(16);
binarySearchTree.add(3);
binarySearchTree.add(5);
binarySearchTree.add(7);
binarySearchTree.add(9);
binarySearchTree.add(11);
binarySearchTree.add(13);
binarySearchTree.add(15);
binarySearchTree.add(17);
binarySearchTree.print(); // => 10 | 6 14 | 4 8 12 16 | 3 5 7 9 11 13 15 17
binarySearchTree.remove(10); // remove 10, 11 goes up
binarySearchTree.print(); // => 11 | 6 14 | 4 8 12 16 | 3 5 7 9 x 13 15 17
binarySearchTree.remove(12); // remove 12; 13 goes up
binarySearchTree.print(); // => 11 | 6 14 | 4 8 13 16 | 3 5 7 9 x x 15 17
console.log('tree is balanced is true:', binarySearchTree.isBalanced()); // => true
console.log('tree is balanced optimized is true:', binarySearchTree.isBalancedOptimized()); // => true
binarySearchTree.remove(13); // remove 13, 13 has no children so nothing changes
binarySearchTree.print(); // => 11 | 6 14 | 4 8 x 16 | 3 5 7 9 x x 15 17
console.log('tree is balanced is false:', binarySearchTree.isBalanced()); // => false
console.log('tree is balanced optimized is false:', binarySearchTree.isBalancedOptimized()); // => false