BST Construction

Binary Search Tree solutions

We are going to implement - search(), insert(), traverse(), and delete() methods that have their respective functionalities.

Binary Search Tree class

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

The BST class has a constructor which has left and right pointers to denote left and right children nodes. They're initialized to null. It also has a value property that contains the actual value in the node.

Insert method

1. Keeping in mind the properties of a BST, i.e. the left children will be less than the current node and right children will be greater than the current node - We first essentially search for the right place.
2. Check if the target insertion element's value is less than the current node we are standing at. If so, we get into the left subtree by writing currentNode = currentNode.left and loop again.
3. If there is NO LEFT CHILD - meaning we have reached the end point - we insert the element there - since insertion can only take place at leaf nodes.
4. Check if the taret insertion element's value is greater than the current node we are standing at. If so, we get into the left subtree by writing currentNode = currentNode.right and loop again.
5. If there is NO RIGHT CHILD - meaning we have reached the end point - we insert the element there - since insertion can only take place at leaf nodes.

Search method

Pretty much the same implementation like insert. In insert method, we first search for the right place and then insert. Here, we are going to simply search based on the properties of a BST.

let currentNode = this;
    while (currentNode !== null) {
      if (value < currentNode.value) {
        currentNode = currentNode.left;
      } else if (value > currentNode.value) {
        currentNode = currentNode.right;
      } else {
        return currentNode;
      }
    }
return null;

1. Compare the value of the target search element with that of the current node you're standing at / currently traversing.
2. If the value === targetNode - search successful - return true.
3. If targetNode < value - Traverse the left subtree
4. if targetNode > value - Traverse the right subtree
5. If you've reached null - return false because the element will not be present in the BST.

Traverse method - Preorder traversal

    let currentNode = this;
    if (currentNode === null) {
      return;
    }
    console.log(currentNode.value);
    currentNode.left && currentNode.left.traverse();
    currentNode.right && currentNode.right.traverse();

Preorder traversal follows the concept of root->left->right. Which means that the value of the root will be printed first, then we will traverse the left subtree and then we will traverse the right subtree.

1. If currentNode is null, return because you've reached the end of the tree.
2. Print the value of the currentNode
3. Traverse left subtree recursively
4. traverse right subtree recursively.

Delete method

For deletion, we have various cases to deal with.

1. If the node being deleted is a leaf node
2. If the node being deleted has a left subtree
3. If the node being deleted has a right subtree
4. If the node being deleted has both left and right children.

Let's look at the algorithm:

1. We start at the root node and declare currentNode = this.
2. If the curentNode is NOT equal to null, we check for the values and traverse to either left or right subtree. That is, we are essentially searching for the element to be deleted first.
3. While doing so, we need to keep track of the parentNode in order to come back at it later since our base case will be null check, we need to make sure we know where we came from.
4. As and we reach the base case, we'll start tackling the above 4 points that are mentioned.

if (currentNode.left !== null && currentNode.right !== null) {
    currentNode.value = currentNode.right.getMinValue();
    currentNode.right.delete(currentNode.value, currentNode);
} 

5. To delete a node that has BOTH left and right children, we either need to take the minimum value from the right subtree OR maximum value from the left subtree. These are called inorder successor and inorder predecessors. The only eligible candidates to replace this current node are either the max element from left, or the min element from the right.

if (currentNode.left !== null) {
  currentNode.value = currentNode.left.value;
  currentNode.right = currentNode.left.right;
  currentNode.left = currentNode.left.left;
} else if (currentNode.right !== null) {
  currentNode.value = currentNode.right.value;
  currentNode.left = currentNode.right.left;
  currentNode.right = currentNode.right.right;
}

6. Here we check for the single node cases. In these cases, We just swap the leaf node with the parent node.