Search⌘ K
Home
Courses
Data Structures for Coding Interviews in JavaScript

Binary Search Tree Insertion (Implementation)

Explore the iterative and recursive techniques for inserting values into a binary search tree using JavaScript. Understand how to maintain tree structure by placing new values correctly, handling empty trees, and using helper functions to streamline recursive calls.

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 ...