Binary Search Trees IV/? - Adding Nodes

Here we are, the long awaited moment for the 5 readers of this series, we have come to adding nodes! There are a couple methods for this, but I'm going to use the recursive method, since it's in line with the way I wrote up traversal, and I think it's neater.

(Before I get started, shout out again to Cracking the Coding Interview, as well as to this guide, which helped me figure all this out.)

So here's our hypothetical situation. Let's do an easy one first. We need to add the number "2" to a binary search tree that's currently empty. Let's create a function that takes in that data as a parameter. This function will be placed inside of the BinarySearchTree class, so we can refer to the tree using the "this" keyword.

function add(data){
    let newNode = new Node(data)
    if (this.root === null){
        this.root = newNode
    };
};

Using the function written above, if we have a variable tree and we call tree.add(2) our empty tree will become a tree with one node of data "2".

That was super easy, but obviously most of the time you won't be so lucky as to be adding your node to an empty tree. So here's another hypothetical. Given the below binary search tree, let's add a node with the number "5."

In this case, the tree is not empty, so we need to decide where to put the new node. Let's compare our piece of data to the data of the current node. We'll make a helper function called addNode that finds the right place to put the node and inserts it.

function add(data){
    let newNode = new Node(data)
    if (this.root === null){
        this.root = newNode
    } else {
        addNode(this.root, newNode);
    };
};

If the new node is less than the current node, we'll know it needs to go somewhere to the left. As is, we see that it is in fact greater than the current node, so it will need to go somewhere to the right. So to start with, our function looks like this:

function addNode(currentNode, newNode){

    if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
    }
};

If there is no right hand child node (if currentNode.right is null) then we know we can insert our new node right there. Let's add in that code.

function addNode(currentNode, newNode){

    if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
        if (currentNode.right === null){
            // if there is no right node, plug in the newNode there!
            currentNode.right = newNode; 
        }
    }
};

Supposing there is a node there already, though, what do we do? We simply repeat this process - examining the node to see if we go left or right. So, we can call on the method itself so that we recurr until we find a node with no right hand child node.

function addNode(currentNode, newNode){

    if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
        if (currentNode.right === null){
            // if there is no right node, plug in the newNode there!
            currentNode.right = newNode; 
        } else {
            // if the right node is not null, recurr until it is!
            addNode(currentNode.right, newNode);
        };
    }
};

If our data happens to be smaller than the current node, we simply do the same thing but headed left

function addNode(currentNode, newNode){

    if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
        if (currentNode.right === null){
            // if there is no right node, plug in the newNode there!
            currentNode.right = newNode; 
        } else {
            // if the right node is not null, recurr until it is!
            addNode(currentNode.right, newNode);
        };
    } else ( // if our newNode is smaller, move left
        if (currentNode.left === null){
            // if there is no left node, plug in the newNode there!
            currentNode.left = newNode; 
        } else {
            // if the left node is not null, recurr until it is!
            addNode(currentNode.left, newNode);
        };
    };

};

So now we have two methods, insert(data) and insertNode(currentNode, newNode). insert creates a new Node from the data provided and checks if the tree is empty. If it is, it fills in the root node with this new one. If it isn't, it passes the buck to insertNode, which is a recursive function that will find the right spot for the new node and add it in.

But wait - what if your data is already in the tree? Here we've worked off the assumption that you are dealing entirely with unique values, but that might not always be the case. There are a few ways to handle this, so rather than cram it into a final paragraph I'll write the next segment on duplicates!

I hope this is helpful to someone - working through it in explicit writing like this is helpful to me.