Inserting values to Binary Search Tree

Node in Binary Search Tree

To insert a node in a binary search tree (bst), we must have a node. A node in a bst has three values:

• Value of the node
• Pointer to the left node
• Pointer to the right node

Node in Binary Search Tree

This is how it looks in the code:

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

Creating a Binary Search Tree

We will create a bst, with one value root. Initially, the binary search tree will have no nodes, so we will assign null to the root.

class BinarySearchTree {
  // start with empty bst
  constructor() {
    this.root = null;
  }
}

Binary Tree with no nodes

Inserting first value in binary search tree

First of all, we will check if the binary search tree is empty, the easy way to do it is to check if the root node is null.

If there are no nodes in bst, we will simply assign the new node to the root node.

if (this.root === null) {
    
      this.root = newNode;
}

Suppose we are inserting 99.

Inserting first element in a Binary Search Tree

That was easy. However, if the root node is not empty, we must insert node to its left or right.

According to the rule of Binary Search Tree,

If the node is less than the root node the value must be set as the left node of bst. And if the value is greater than the root node, it must be set as the right node of the bst.

Inserting value at left of Binary Search Tree

let currentNode = this.root;
while (true) {
        // check if the value is less than root node
        if (value < currentNode.value) { {
          if (!currentNode.left) {
            // set newNode as left
            currentNode.left = newNode;
            // get out of the loop
            return this;
          }
          currentNode = currentNode.left;
        }
}

Let’s say we have to insert 11, to the bst.

We will assign the root node 99 to the currentNode.

Then, we must check if the 11 is less than the currentNode. As 11 is less than 99, it must be inserted to the left of the root node.

Before inserting 11, to the left, we should check if the currentNode already has a left child. As the currentNode doesn’t have a left child, we can insert the new node to the left of the root node. And return from the function.

Inserting in Binary Search Tree

Now, let’s say we have to insert 9 to the bst.

We will assign the root node 99 to the currentNode.

Then, we must check if the 9 is less than the currentNode. As 9 is less than 99, it must be inserted to the left of the root node.

Before inserting 9, to the left, we should check if the currentNode already has a left child. As the currentNode has a left child 11, we set the value of currentNode as 11.

Now, we compare 9 to the currentNode 11. As 9 is less than 11, it must be inserted to the left of the currentNode 11. Before inserting 9, to the left of currentNode, we should check if the currentNodealready has a left child. As 11 doesn’t have a left child we can insert 9 as the left child of 11. And return from the function.

Inserting node to the right of the binary tree

let currentNode = this.root;
while (true) {
        // check if the value is less than root node
        if (value < currentNode.value) {
          if (!currentNode.left) {
            // set newNode as left
            currentNode.left = newNode;
            // get out of the loop
            return this;
          }
          currentNode = currentNode.left;
        } else {
          // check if the right node is empty
          if (!currentNode.right) {
            currentNode.right = newNode;
            return this;
          }
          currentNode = currentNode.right;
        }
      }

Let’s say we have to insert 111, to the bst.

We will assign the root node 99 to the currentNode.

As 111 is greater than 99, it must be inserted to the right of the root node.

Before inserting 111, to the right we should check if the currentNode already has a right child. As the currentNode doesn’t have a right child, we can insert the new node to the right of the root node. And return from the function.

Now, let’s say we have to insert 222 to the bst.

We will assign the root node 99 to the currentNode.

As 222 is greater than 99, it must be inserted to the right of the root node.

Before inserting 222, to the right, we should check if the currentNode already has the right child. As the currentNode has a right child 111, we set the value of currentNode as 111.

Now, we compare 222 to the currentNode111. As 222 is greater than 111, it must be inserted to the right of the currentNode 111. Before inserting 222, to the right of currentNode 111, we should check if the currentNode already has the right child. As 111 doesn’t have a right child we can insert 222 as the right child of 111. And return from the function.

Complete Code

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  // start with empty bst
  constructor() {
    this.root = null;
  }
// insert value in bst
  // keep the rules of bst in mind
  insert(value) {
    // a node to insert
    const newNode = new Node(value);
// check if bst is empt
    if (this.root === null) {
    
      this.root = newNode;
    }
// if root node is not empty
    else {
      // assign the value of rootnode to a variable (to traverse)
      let currentNode = this.root;
      // loop till we find a place for newNode
      while (true) {
      
        if (value < currentNode.value) {
if (!currentNode.left) {
      
            currentNode.left = newNode;
            // get out of the loop
            return this;
          }
          // if there is left child assignj the value of left node to the current node
          currentNode = currentNode.left;
        } else {
          // check if the right node is empty
          if (!currentNode.right) {
            currentNode.right = newNode;
            return this;
          }
          currentNode = currentNode.right;
        }
      }
    }
  }
}
const bst = new BinarySearchTree();
bst.insert(99);
bst.insert (11);
bst.insert(9);
bst.insert(111);
bst.insert(222);
// to have a better view in result
console.log(JSON.stringify(bst));

Output

{“root”:{“value”:99,”left”:{“value”:11,”left”:{“value”:9,”left”:null,”right”:null},”right”:null},”right”:{“value”:111,”left”:null,”right”:{“value”:222,”left”:null,”right”:null}}}}