binary-tree.js

function BST( value ) {
  this.left = null;
  this.right = null;
  this.value = value;
}

BST.prototype.insertNode = function( value ) {
  if ( value < this.value ) {
    if ( !this.left ) {
      this.left = new BST( value );
    } else {
      this.left.insertNode( value );
    }
  } else {
    if ( !this.right ) {
      this.right = new BST( value );
    } else {
      this.right.insertNode( value );
    }
  }
}

BST.prototype.getMin = function() {
  if ( this.left ) {
    return this.left.getMin();
  } else {
    return this.value;
  }
}

BST.prototype.getMax = function() {
  if ( this.right ) {
    return this.right.getMax();
  } else {
    return this.value;
  }
}

BST.prototype.depthFirstTraversal = function( iteratorFunc ) {
  if ( this.right ) {
    this.right.depthFirstTraversal( iteratorFunc );
  }
  iteratorFunc(this.value);
  if ( this.left ) {
    this.left.depthFirstTraversal( iteratorFunc );
  }
}

BST.prototype.breadthFirstTraversal = function( iteratorFunc ) {
  var queue = [ this ];

  while( queue.length ) {
    var treeNode = queue.shift();
    iteratorFunc( treeNode.value );

    if( treeNode.left ) {
      queue.push( treeNode.left );
    }

    if ( treeNode.right ) {
      queue.push( treeNode.right );
    }
  }
}

BST.prototype.count = function( total = 0 ) {
  var queue = [ this ];
  var total = 1;

  while ( queue.length ) {
    var node = queue.shift();

    if ( node.left ) {
      queue.push(node.left);
      total++;
    }

    if ( node.right ) {
      queue.push(node.right);
      total++;
    }
  }

  return total;
}

BST.prototype.contains = function( value ) {
  if (this.value === value) {
    return true;
  }

  if ( value < this.value ) {
    if ( !this.left ){
      return false;
    } else {
      return this.left.contains(value);
    }
  } else {
    if ( !this.right ) {
      return false;
    } else {
      return this.right.contains(value);
    }
  }
}

function iteratorFunc(val) {
  console.log(val);
}

BST.prototype.remove = function( value ) {
  if ( value < this.value ) {
    if ( this.left ) {
      if ( this.left.value === value ) {
        if (! this.left.left && ! this.left.right  ) {
          this.left = null;
        }

        if ( this.left.left && this.left.right ) {
          this.left.right.left = this.left.left;
          this.left = this.left.right;
        }

        if ( this.left.left && ! this.left.right ) {
            this.right = this.right.left;
          }

          if ( ! this.left.left && this.left.right ) {
            this.left = this.left.right;
          }

      } else {
        this.left.remove(value);
      }
    }
  } else {
    if ( this.right ) {
      if ( this.right.value === value ) {
        if ( ! this.right.left && ! this.right.right ) {
          this.right = null;
        }

        if ( this.right ) {
          if ( this.right.left && this.right.right ) {
            this.right.left.right = this.right.right;
            this.right = this.right.left;
            this.right.left = null;
          }

          if ( this.right.left && ! this.right.right ) {
            this.right = this.right.left;
          }

          if ( ! this.right.left && this.right.right ) {
            this.right = this.right.right;
          }
        }
      } else {
        this.right.remove(value);
      }
    }
  }
}

var bst = new BST( 50 );

bst.insertNode( 30 );
bst.insertNode( 20 );
bst.insertNode( 40 );
bst.insertNode( 100 );
bst.insertNode( 70 );
bst.insertNode( 105 );
bst.insertNode( 35 );
bst.insertNode( 45 );
bst.insertNode( 101 );
bst.insertNode( 110 );
bst.insertNode( 15 );
bst.insertNode( 25 );
bst.insertNode( 107 );
bst.insertNode( 125 );
bst.insertNode( 43 );

bst.remove( 45 );