BinarySearchTreeNode.js

import BinaryTreeNode from '../BinaryTreeNode';
import Comparator from '../../../utils/comparator/Comparator';

export default class BinarySearchTreeNode extends BinaryTreeNode {
  /**
   * @param {*} [value] - node value.
   * @param {Object} [meta] - any meta information that is attached to the node.
   * @param {function} [compareFunction] - comparator function for node values.
   */
  constructor(value = null, meta = null, compareFunction = undefined) {
    super(value, meta);

    // This comparator is used to compare node values with each other.
    this.compareFunction = compareFunction;
    this.nodeValueComparator = new Comparator(compareFunction);
  }

  /**
   * @param {*} value
   * @param {Object} [meta]
   * @return {BinarySearchTreeNode}
   */
  insert(value, meta = null) {
    if (this.nodeValueComparator.equal(this.value, null)) {
      this.value = value;
      this.meta = meta;

      return this;
    }

    if (this.nodeValueComparator.lessThan(value, this.value)) {
      // Insert to the left.
      if (this.left) {
        this.left.insert(value, meta);
      } else {
        this.setLeft(new BinarySearchTreeNode(value, meta, this.compareFunction));
      }
    } else if (this.nodeValueComparator.greaterThan(value, this.value)) {
      // Insert to the right.
      if (this.right) {
        this.right.insert(value, meta);
      } else {
        this.setRight(new BinarySearchTreeNode(value, meta, this.compareFunction));
      }
    }

    return this;
  }

  /**
   * @param {*} value
   * @return {BinarySearchTreeNode}
   */
  find(value) {
    // Check the root.
    if (this.nodeValueComparator.equal(this.value, value)) {
      return this;
    }

    if (this.nodeValueComparator.lessThan(value, this.value) && this.left) {
      // Check left nodes.
      return this.left.find(value);
    } else if (this.nodeValueComparator.greaterThan(value, this.value) && this.right) {
      // Check right nodes.
      return this.right.find(value);
    }

    return null;
  }

  /**
   * @param {*} value
   * @return {boolean}
   */
  contains(value) {
    return !!this.find(value);
  }

  /**
   * @param {*} value
   */
  remove(value) {
    const nodeToRemove = this.find(value);

    if (!nodeToRemove) {
      throw new Error('Item not found in the tree');
    }

    const { parent } = nodeToRemove;

    if (!nodeToRemove.left && !nodeToRemove.right) {
      // Node is a leaf and thus has no children.
      // Just remove the pointer to this node from the parent node.
      parent.removeChild(nodeToRemove);
    } else if (nodeToRemove.left && nodeToRemove.right) {
      // Node has two children.
      // Find the next biggest value (minimum value in the right branch)
      // and replace current value node with that next biggest value.
      const nextBiggerNode = nodeToRemove.right.findMin();
      if (!this.nodeComparator.equal(nextBiggerNode, nodeToRemove.right)) {
        this.remove(nextBiggerNode.value);
        nodeToRemove.value = nextBiggerNode.value;
      } else {
        // In case if next right value is the next bigger one and it doesn't have left child
        // then just replace node that is going to be deleted with the right node.
        nodeToRemove.value = nodeToRemove.right.value;
        nodeToRemove.right = nodeToRemove.right.right;
      }
    } else {
      // Node has only one child.
      // Make this child to be a direct child of current node's parent.
      if (nodeToRemove.left) {
        parent.replaceChild(nodeToRemove, nodeToRemove.left);
      } else {
        parent.replaceChild(nodeToRemove, nodeToRemove.right);
      }
    }
  }

  /**
   * @return {BinarySearchTreeNode}
   */
  findMin() {
    if (!this.left) {
      return this;
    }

    return this.left.findMin();
  }
}