Data Structures for Coding Interviews in C++/

...

/

Binary Search Tree Insertion (Implementation)

Binary Search Tree Insertion (Implementation)

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

We'll cover the following...

Introduction #

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,5,2,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 insertBST function as part of the BinarySearchTree class is as follows:

C++
void insertBST(int val) {
    if(getRoot()==NULL){
            root=new Node(val);
            return;
    }
    //starting from the root
    Node* currentNode = root;
    Node* parent;
    //while we get to the null node
    while (currentNode) {
        parent = currentNode; //update the parent
        if (val < currentNode->value) {
            //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 (val < parent->value) {
        //if newValue < parent.val
        //insert into the leftChild
        parent->leftChild = new Node(val);
    } else {
        //if newValue >= parent.val
        //insert into the rightChild
        parent->rightChild = new Node(val);
    }
}

Let’s now put this function in our class and insert some values into our ...