binary search tree construction

In this tutorial, i am going to show you examples of how to construct a binary search tree (BST). Specifically i will show you how to:

1. Insert values with the insert method
2. Remove values with the remove method
3. Search for values with the contains method

How to create a binary search tree from a list of numbers

Given a list of numbers {10, 5, 15, 2, 5, 13, 22, 1, 14}, to be able to construct the BST accurately, you must first of all know that: every binary search tree node has an integer value, a left child node and a right child node. A node is said to be a valid BST node if and only if all the nodes to the left of the node is less than the node and all the nodes to the right of the node is greater than or equals to the node. A node may not have more than 2 children but may have just 1 child (either a left or a right child) or none.

The constructed BST above is a valid Binary search tree because:

• Node 5 is less than node 10; so node 5 is valid as the left child of node 10.
• Node 15 if greater than node 10; so node 15 is valid as the right child of node 10.
• Node 2 is less than node 5, so node 2 is valid as the left child of node 5.
• Node 5 is equal to node 5, so node 5 is valid as the right child of node 5 etc.
• No node has more that 2 nodes attached to it.
• Every node has either 2 nodes, 1 node or no node attached to it

To construct the BST, we will create a c++ class called BST with the 3 operations: insertion, remove and contains. But before we start, i want you to take a look at the image below to see the structure of a BST node captured using the debugger.

Look at the part marked with x and you will notice that this is the first node (i.e the node with value 10) in our constructed BST image above. Notice that the node has an address: 0x23fc5151960, a value 10; a left child node with an address: 0x23fc51519b0 and a right child node with an address: 0x23fc5153bb0.

This structure is so because each node is declared either as a struct or a class with the following code

class BST {
public:
    int value;
    BST *left;
    BST *right;

    BST(int val) {
        value = val;
        left = nullptr;
        right = nullptr;
    }
}

Notice that the left and the right properties of the class BST are declared as Pointers of the same BST, hence the reason why both variables store addresses and also the reason why all properties and operations of the BST class are available to them. To confirm what i am saying, if you click on the left or right > sign shown in the image above, you find that left has left and right as sub nodes and so on, likewise right also has left and right as sub nodes and so on.

This time notice that node’s 5 left child node and right child node stores 0x0 (i.e null) instead of a full address, likewise node’s 15 also. This indicate that both node 5 and node 15 who are node’s 10 left child node and right child node are leaf’s node; in other words, the BST has only 3 nodes

So to create the very first node of our BST with the value 10, all i need to do is to instantiate our BST class object thus:

BST *newNode = new BST(10);

Because of the new keyword used to create the object of the class BST, a memory is allocated dynamically on the heap and its address is stored in the pointer variable newNode; hence newNode now holds the value: 0x23fc5151960 – your computer may assign a different number.

BST Insertion Operation

Now that we have created the first node, to continue inserting new nodes into our BST, we call the insertion method of our BST class. Insertion follows the BST rules already describes above.

newNode->insert(5);
newNode->insert(15);

So the node 5 is then inserted as node’s 10 left child because 5 < 10 and node 15 is inserted as node’s 10 right child because node 15 > 10.

As you can see in the full code below, i have declared the insert function to return a reference of the current state of the BST class with this line of code: BST &insert(int val) and i have also returned a dereferenced *this – which returns the present state of the BST class.

Full BST construction code in c++

class BST {
public:
    int value;
    BST *left;
    BST *right;

    BST(int val) {
        value = val;
        left = nullptr;
        right = nullptr;
    }
    BST &insert(int val) {
        // Write your code here.		
        if(val < value){
            if(left == nullptr){
                BST *newNode = new BST(val);
                left = newNode;
            }else{
                left->insert(val);
            }
        }
        if(val >= value){
            if(right == nullptr){
                BST *newNode = new BST(val);
                right = newNode;
            }else{
                right->insert(val);
            }
        }
        // Do not edit the return statement of this method.
        return *this;
    }
    bool contains(int val) {
        // Write your code here.
        static bool res = false;

        if(val == value){
            return true;
        }
        if(val < value){
            if(left == nullptr){
                return false;
            }else{
                res = left->contains(val);
            }
        }
        if(val > value){
            if(right == nullptr){
                return false;
            }else{
                res = right->contains(val);
            }
        }
        return res;
    }
    int Get_min_value_of_root_right(BST *root){
        static BST *prev = nullptr;
        if(root == nullptr){
            return prev->value;
        }
        prev = root;
        root = root->left;
        int minVal = Get_min_value_of_root_right(root);

        return minVal;
    }
    BST &remove(int val) {
        // Write your code here.
        static BST *root = this;
        static BST *prev = nullptr;
        if(root == nullptr) return *this;

        if(val < value){
            if(root->left != nullptr){
                prev = root;
                root = root->left;
                root->remove(val);
            }
        }else if(val > value){
            if(root->right != nullptr){
                prev = root;
                root = root->right;
                root->remove(val);
            }
        }else{
            if(root->left == nullptr && root->right == nullptr){
                delete root;
                prev->left = nullptr;
                return *this;
            }
            if(root->left == nullptr){
                BST *temp = root->right;//assign right node to temp node
                delete root;//delete node
                prev->right = temp;//point prev node to temp node
            }
            if(root->right == nullptr){
                BST *temp = root->left;//assign left node to temp node
                delete root;//delete node
                prev->left = temp;//point prev node to temp node
            }
            if(root->left != nullptr && root->right != nullptr){
                //get right's minimum value
                int minVal = Get_min_value_of_root_right(root->right);
                //re-assign root with minVal
                root->value = minVal;
                root = root->right;//avoid round-robin
                //delete right's minimum value
                root->remove(minVal);
            }
        }
        // Do not edit the return statement of this method.
        return *this;
    }
};

BST Remove Operation

There are three conditions to consider when coding the remove operation a BST; they are:

1. The node to be deleted is a leaf node, i.e the both the left child node and the right child node is null. In this case you just go ahead and delete the node without any further action.
2. Either the left child node or the right child node is null. If the left child node is null, assign right node to a temporary node (which i call temp in the code), delete the node and then point the node before the node to be deleted (which i call prev in the code) to the temporary node. Do vice versa (as shown in the code) if the right child node of the node to be deleted is null.
3. If both the left child node and the right child node of the node to be deleted is not null. If this is the case, then we have to find the min value of the right sub tree of the node to be deleted; when we obtain that min value, we will re-assign the node’s value to be deleted with the min value; by this time there will be two nodes with the same min value: the node where the min value was obtained from and the node to be deleted. Now will should delete the node where the min value was obtained from instead of the original node that we intended to delete. So we ended up not deleting the original node we intended to delete but instead just changed its value. The reason we are doing so is because we need to maintain the BST rule; all nodes to the left of a node must be less than the node and all nodes to the right of a node must be greater than or equal to the node.

But notice from the code that before we find the particular node to be deleted, we first of all check if the the node to be deleted lies to the left of the root node or to the right of the root node by checking if the value of the node to be deleted is less than or greater than the root node. If less than we go left, if greater than we go right; we continue to do the same check for each sub tree until we finally arrive at a node where the value is equal to the value of the node to be deleted. The contains operation carry a similar algorithm, the only difference is that when we find the node we are searching for, we return true and if not found we return false.