Binary search tree data structure implementation in C++

Binary Search Tree (a.k.a BST): is a useful data structure which has an important role in sorting, in addition, it is useful for other data structure like a set.

Binary Search Tree is not added to STL ( standard template library), so here despite explanation, I will show how to implement Binary Search Tree.

The Binary Search Tree’s rules

1: Binary Search Tree has a unique value which means no repeated value is accepted in a tree

2: The left child (Left subtree)  must have a lower value than the current node

3: It’s right child (right subtree)  must have a greater value.

A sample of implementation Binary Search Tree code in c++

struct BST
{
    int value;
    BST* left;
    BST* right;
};

Insertion in Binary Search Tree

For insertion to a Binary Search tree, there are some steps to follow

1: To check whether the root (the current node) is null or equal?

If it is null or the value of it is equal to the item then assign the item to the root

2: If the root is not NULL then check whether it is greater or smaller

2.1: If it is lower than the current node(root) then we repeat the above steps for left child

2.1: If it’s greater then we repeat the above steps for the right child

The image below shows step by step checking of the place of the value. First image inserts the 3 and second image inserts the 14.

Code | Implementation of insertion in Binary Search Tree

void insert_bst(BST* &node, BST* newNode)
{
    if(node == NULL)
        node == newNode;
    if(newNode->value < node->value)
        insert_bst(node->left, newNode);
    if(newNode->value > node->value)
        insert_bst(node->right, newNode);
}

Deletion in Binary Search Tree

For deletion a node in Binary search tree there are 3 possibilities

1: Deletion a node with no child(leaf): deleting a leaf is easy in Binary Search tree, just         point the pointer  (which is pointing the current node ) to NULL

2: Deletion of a node with one child: in this case after deleting the node its child takes its place or just pointer its pointer to its child.

3: Deletion a node with two child: in this case after deleting the node there are two possible way to do you are free to do any of them, first the most left child of right child of current node takes the place of deleted node, second the most right child of left child of current node takes the place of deleted node.

Code | Implementation of deleting a node in Binary Search Tree

for implementing deletion a node we need another function to write for find the leftmost child or rightmost child as here I use to find the leftmost child you can write for any

BST* leftMostChild(BST* node)
{
    if(node->left == NULL)
        return node;
    else
        leftMostChild(node->left);
}
void free(BST* tree)
{
    tree == NULL;
}
bool delete_node(BST* node, int value)
{
    BST* successor;
    BST* deleteNode;

    if(node)
    {
        if(node->value < value)
            delete_node(node->right, value);
        else if(node->value > value)
            delete_node(node->right, value);
        else
        {
            if(node->left == NULL)
            {
                deleteNode = node;
                node = node->right;
                free(deleteNode);
            }
            else if(node->right == NULL)
            {
                deleteNode = node;
                node = node->left;
                free(deleteNode);
            }
            else
            {
                successor = leftMostChild(node->right);
                node->value = successor->value;
                return delete_node(node->right, successor->value);
            }
            return true;
        }
    }
    else
        return false;
}

Search for an item in a Binary search tree

Searching an item in the binary search tree is an easy task, it works the same as insertion. Finding the item we need three steps to follow

1: Check whether the current node (root) is NULL, If its NULL return -1

2: If it’s not NULL check if it’s equal

2.1 If it’s equal then return it

2.2 If it’s greater than the current node then repeat the above steps for the right child (right subtree)

2.3 If it’s lesser than the current node then repeat the above steps for the left child (left subtree)

Code for searching a key in Binary Search Tree

int search_bst(BST* node, int key)
{
    if(node == NULL)
        return -1;
    if(key > node->value)
        search_bst(node->right, key);
    if(key < node->value)
        search_bst(node->left, key);
    else
        return node->value;
}

Traversing Binary Search tree

There are three ways to print a binary search tree

1. Pre-order: in this case first print the root then  print the left child and in last print the right child

2. In-order: in  this case first print the left child then print the root and in last print the right child

3. Post-order: in this case, firs print the right child then print the left child and in last print the root

Here is the code or implementation of Traversing a Binary Search Tree

The code is for in-order traversing you can write for any

void printBSTINORDER(BST* tree)
{
    if(tree == NULL)
        return;
    printBSTINORDER(tree->left);
    cout<<(tree->value)<<" ";
    printBSTINORDER(tree->right);
}

The time complexity for deletion | insertion | Searching in Binary search tree is:

                                Average case is equal to:                    O(logn)

                                worst case is equal to:                          O(n)