Data Structures for Coding Interviews in JavaScript/

...

/

Binary Search Tree Insertion (Implementation)

Binary Search Tree Insertion (Implementation)

In this lesson, we'll study the implementation of Binary Search Tree insertion in JavaScript through the iterative and recursive approaches.

We'll cover the following...

There are two ways to code a BST insert function

  • Iteratively
  • Recursively

We will be implementing both in this lesson.

We’ll end up with the following tree once we implement the BST insert function and insert the elements [6,4,9,2,5,8,12,10,14].

%0 6 6 8 9 6->8 4 4 6->4 7 8 8->7 12 12 8->12 5 5 4->5 3 2 4->3 10 10 12->10 14 14 12->14

Insert Implementation (Iterative) #

The iterative implementation of the insert function as part of the BinarySearchTree class is as follows:

Node.js
insert(newValue) {
    if(this.root==null){
        this.root=new Node(newValue);
        return;
    }
    //starting from the root
    var currentNode = this.root;
    var parent;
    //while we get to the null node  
    while (currentNode) {
        parent = currentNode; //update the parent
        if (newValue < currentNode.val) {
            //if newValue < currentNode.val, 
            //iterate to the left subtree
            currentNode = currentNode.leftChild
        } else {
            //if newValue >= currentNode.val, 
            //iterate to the right subtree
            currentNode = currentNode.rightChild;
        }
    }
    //by now, we will have the parent of the null
    //node where we have to insert the newValue 
    if (newValue < parent.val) {
        //if newValue < parent.val
        //insert into the leftChild
        parent.leftChild = new Node(newValue)
    } else {
        //if newValue >= parent.val
        //insert into the rightChild
        parent.rightChild = new Node(newValue)
    }
}

Now let’s put ...