Using JS to implement the operation of binary search tree(BST)

binary-search-tree.js

/**
 * Create a tree node
 *
 * @function createTreeNode
 * @param {Number} key     Key of the node to distinguish with others
 * @param {*}      data    Data belongs to the node. If data is not given, it equals to key.
 * @return {Object} Tree node
 */
const createTreeNode = (key, data=key) => ({
  key,
  data,
  leftChild: null,
  rightChild: null
});

/**
 * Insert node in binary search tree
 *
 * @function insertNode
 * @param {Object} parent          Root node of binary search tree
 * @param {Object} insertedNode    The node which is going to insert
 * @return {Boolean} result of insertion    Only when the key exists return false, otherwise, Return true.
 */
const insertNode = (parent, insertedNode) => {
  if (insertedNode.key === parent.key) {
    return false;
  } else if (insertedNode.key < parent.key && parent.leftChild) {
    return insertNode(parent.leftChild,insertedNode);
  } else if (insertedNode.key < parent.key) {
    parent.leftChild = insertedNode;
  }  else if (insertedNode.key > parent.key && parent.rightChild) {
    return insertNode(parent.rightChild,insertedNode);
  } else {
    parent.rightChild = insertedNode;
  }

  return true;
};

/**
 * Find node from the current node and its subtree in binary search tree
 *
 * @function findNode
 * @param {Object} currentNode    Root node of binary search tree
 * @param {Number} key            The search key
 * @return {Boolean} Status of search    If it does find the node with the key, return true, otherwise, return false.
 */
const findNode = (currentNode, key) => {
  if (key < currentNode.key && currentNode.leftChild) {
    // To find the smaller key in left subtree
    return findNode(currentNode.leftChild, key);
  } else if (key > currentNode.key && currentNode.rightChild) {
    // To find the larger key in right subtree
    return findNode(currentNode.rightChild, key);
  } else {
    // Is the currentNode with the key?
    return currentNode.key === key;
  }
};

/**
 * Find the minimum key in a binary search tree
 *
 * @function findMin
 * @param {Object} BST    The root node of binary search tree
 * @return {Object}    The node with the minimum key
 */
const findMin = (BST) => {
  let currentNode = BST;

  while (currentNode.leftChild) {
    currentNode = currentNode.leftChild;
  }

  return currentNode;
};

/**
 * Find the maximum key in a binary search tree
 *
 * @function findMax
 * @param BST    The root node of binary search tree
 * @return {Object}    The node with the maximum key
 */
const findMax = (BST) => {
  let currentNode = BST;

  while (currentNode.rightChild) {
    currentNode = currentNode.rightChild;
  }

  return currentNode;
};

/**
 * Delete the node with the giving key in binary search tree
 *
 * @function deleteNode
 * @param {Object} currentNode    Current node in traversal
 * @param {Number} key            The giving key
 * @param {Object} parent         The parent of current node. At the beginning, it equals to the currentNode by default.
 * @return {boolean} status of deletion    If it does delete the node with the key, return true, otherwise, return false.
 */
const deleteNode = (currentNode, key, parent=currentNode) => {
  if (key < currentNode.key && currentNode.leftChild) {           // -------
    return deleteNode(currentNode.leftChild, key, currentNode);   // |
  } else if (key < currentNode.key) {                             // |  try to find the key but not find it
    return false;                                                 // |
  } else if (key > currentNode.key && currentNode.rightChild) {   // |  return false
    return deleteNode(currentNode.rightChild, key, currentNode);  // |
  } else if (key > currentNode.key) {                             // -------
    return false;                                                 
  } else {                                                        // #####################
    if (                                                          //    below: the key has been found, do deletion
      !currentNode.leftChild &&                                   // #####################
      !currentNode.rightChild &&                                  // -------
      Object.is(currentNode, parent.leftChild)                    // |
    ) {                                                           // |  [Condition]:
      parent.leftChild = null;                                    // |  the current node is a leaf node, no children
      currentNode = null;                                         // |
    } else if (                                                   // |  [Handling]:
      !currentNode.leftChild &&                                   // |  just clean the current node and its connection
      !currentNode.rightChild &&                                  // |  to parent
      Object.is(currentNode, parent.rightChild)                   // |
    ) {                                                           // |
      parent.rightChild = null;                                   // |
      currentNode = null;                                         // -------
    } else if (
      currentNode.leftChild &&                                    // -------
      !currentNode.rightChild &&                                  // |
      Object.is(currentNode, parent.leftChild)                    // |
    ) {                                                           // |
      parent.leftChild = currentNode.leftChild;                   // |
      currentNode = null;                                         // |
    } else if (                                                   // |  [Condition]:
      !currentNode.leftChild &&                                   // |  the current node have one child(left or right),
      currentNode.rightChild &&                                   // |  the current node is the left or right child
      Object.is(currentNode, parent.leftChild)                    // |  of the parent node
    ) {                                                           // |
      parent.leftChild = currentNode.rightChild;                  // |  (the total kinds of condition is 4)
      currentNode = null;                                         // |
    } else if (                                                   // |  [Handling]:
      currentNode.leftChild &&                                    // |  connect the child of the current node,
      !currentNode.rightChild &&                                  // |  and clean the current node
      Object.is(currentNode, parent.rightChild)                   // |
    ) {                                                           // |
      parent.rightChild = currentNode.leftChild;                  // |
      currentNode = null;                                         // |
    } else if (                                                   // |
      !currentNode.leftChild &&                                   // |
      currentNode.rightChild &&                                   // |
      Object.is(currentNode, parent.rightChild)                   // |
    ) {                                                           // |
      parent.rightChild = currentNode.rightChild;                 // --------
      currentNode = null;
    } else {
      // the current node has 2 children
      // in order to maintain the BST structure with the minimum change
      // we need to find a node in subtree of the current node to replace it
      // the node with maximum key in the left subtree and the node with minimum key in the right tree are both suitable
      // just get the key, data of replacing node and delete the replacing node
      let replacingNode = {...findMin(currentNode.rightChild), leftChild: null, rightChild: null};
      // replace the current node with the minimum key of right subtree
      currentNode.key = replacingNode.key;
      currentNode.data = replacingNode.data;

      deleteNode(currentNode.rightChild, replacingNode.key, currentNode);
    }

    // delete node successfully
    return true;
  }
};

/**
 * Logging the key of tree node in ascending order in the binary search tree
 *
 * @function inOrderTraversal
 * @param {object} node    Root node of binary search tree
 */
const inOrderTraversal = (node) => {
  if (node.leftChild) {
    inOrderTraversal(node.leftChild);
  }

  console.log(node.key);

  if (node.rightChild) {
    inOrderTraversal(node.rightChild);
  }
};

const createBinarySearchTree = () => {
  const root = createTreeNode(50);

  const node_2 = createTreeNode(12);
  const node_3 = createTreeNode(100);
  const node_4 = createTreeNode(64);
  const node_5 = createTreeNode(78);
  const node_6 = createTreeNode(45);
  const node_7 = createTreeNode(36);
  const node_8 = createTreeNode(57);

  insertNode(root, node_6);
  insertNode(root, node_4);
  insertNode(root, node_2);
  insertNode(root, node_5);
  insertNode(root, node_7);
  insertNode(root, node_3);
  insertNode(root, node_8);

  return root;
};

// --------------------------- testing ---------------------------

const binarySearchTree = createBinarySearchTree();


console.log('-------- Binary Search Tree --------');
console.log(binarySearchTree);

// console.log('-------- Test findNode() -------');
// console.log(findNode(binarySearchTree, 12));
// console.log(findNode(binarySearchTree, 36));
// console.log(findNode(binarySearchTree, 45));
// console.log(findNode(binarySearchTree, 50));
// console.log(findNode(binarySearchTree, 57));
// console.log(findNode(binarySearchTree, 64));
// console.log(findNode(binarySearchTree, 78));
// console.log(findNode(binarySearchTree, 100));
//
// console.log(findNode(binarySearchTree, 42));

console.log('-------- In-Order Traversal --------');
inOrderTraversal(binarySearchTree);

console.log('-------- Test findMax() --------');
console.log(findMax(binarySearchTree));
console.log('-------- Test findMin() --------');
console.log(findMin(binarySearchTree));

console.log('-------- Test deleteNode() --------');
console.log(deleteNode(binarySearchTree, 45));
console.log('-------- In-Order Traversal --------');
inOrderTraversal(binarySearchTree);

console.log('-------- Test deleteNode() --------');
console.log(deleteNode(binarySearchTree, 78));
console.log('-------- In-Order Traversal --------');
inOrderTraversal(binarySearchTree);

console.log('-------- Test deleteNode() --------');
console.log(deleteNode(binarySearchTree, 32));
console.log('-------- In-Order Traversal --------');
inOrderTraversal(binarySearchTree);