Binary Search Tree in C/C++

Filed Under: C++
Binary Search Tree

In this article, we’ll take a look at implementing a Binary Search Tree in C/C++.

A Binary Search Tree(BST) is a Binary Tree in which every element of a left sub-tree is less than the root node, and every element in the right sub-tree is greater than it.

This definition applies to every node in the tree, starting from the root node.

For example, the below figure shows a Binary Search Tree.

Bst Example
Binary search tree Example

Here, the left sub-tree from the root contains elements lesser than it, and the right sub-tree has those greater than it. This also applies to every node in the tree, as you can observe.

Due to this, BSTs are often called “sorted binary trees”, since an in-order traversal (refer to this article for what it means) will give a sorted list of elements.

Let us now understand some of the concepts involved, before implementing them.


Create the Data Structures for the Binary Search Tree in C/C++

Let’s write the structures and some helper functions for our BST.

Any Binary Search Tree node has a data element, along with pointers to it’s left and right children. It also has a marker is_leaf, to check if it’s a leaf node.

Let’s write our structure now

typedef struct TreeNode {
    // TreeNode structure for the Binary Search Tree (BST)
    // A BST has the left subtree being less than the root,
    // while the right subtree is greater than the root
    int data; // A Node contains data
    struct TreeNode* left, *right; // As well as pointers to the left and right children
    int is_leaf; // Check whether a node is a leaf node or not
}TreeNode;

Now, we’ll make a function to create a new tree node, that initializes the parameters.

TreeNode* make_treenode(int data) {
    // Construct a treenode pointer using data
    TreeNode* node = (TreeNode*) calloc (1, sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    node->is_leaf = 1;
    return node;
}

Let’s also write a function that frees our complete Binary Search Tree in C/C++ from memory.

void free_bst(TreeNode* root) {
    // Frees the complete BST from memory
    if (!root)
        return;
    free_bst(root->left);
    free_bst(root->right);
    free(root);
}

Let’s now move onto the insert_bst() method, that inserts a node into the BST.

Inserting Data into a Binary Search Tree

Any Binary Search Tree (BST) has the property that:

  • The left sub-tree has elements of less value than the root node
  • The right sub-tree has elements greater than the root node

So, if we want to insert a node, we must ensure that our node must have its correct position, by comparing the key of the node with the current root.

To visualize how the insertion is being done, let’s take an example.

Consider the below tree, with only one node.

Bst Step One
Bst Step One

Let’s insert 20 to this tree. Since 45 > 20, we must insert it to the left sub-tree. Since our sub-tree is empty, we can directly add to it.

Bst Step Two
Bst Step Two

Now, let’s insert 15. Since 15 < 45, we insert to the left sub-tree and update the current root. Now again, we check with the current root (20). 15 < 20, so we again move to the left and insert it.

Bst Step Three
Bst Step Three

Let’s insert 60 now. Since 60 > 45, we insert to the right.

Bst Step Four
Bst Step Four

Similarly, you can insert the elements 40, 50 and 70 to get our final BST.

Bst Example 1
Bst Example 1

The algorithm for insertion is as follows:

  • Start at the root node of the tree. If it does not exist, simply make the new node as the root node and return it!
  • Otherwise, we must compare the key of the node to be inserted and the key of the root.
  • If the key of the node is lesser than the root, we need to insert it to the left sub-tree
  • Otherwise, insert to its right sub-tree.

Our method has the signature of:

TreeNode* insert_bst(TreeNode* root, int data);

This takes the pointer to the root node and inserts data into it.

If the root node is NULL (doesn’t exist), we simply create a new node using data and assign it as the new root node.

TreeNode* insert_bst(TreeNode* root, int data) {
    // Inserts data into it's appropriate position
    // in the BST
    if (!root) {
        // Make the root node
        root = make_treenode(data);
        return root;
    }
    else {
        // TODO: Insert to the existing root
        return root;
    }
}

Let’s now move on to the else part, if we need to insert it to an existing node. We simply follow the algorithm described above, with additional checks for the leaf node base case.

The comments in the code should be self-explanatory. We insert to the left sub-tree if data < root->data and to the right, if data > root->data.

TreeNode* insert_bst(TreeNode* root, int data) {
    // Inserts data into it's appropriate position
    // in the BST
    if (!root) {
        // Make the root node
        root = make_treenode(data);
        return root;
    }
    else {
        // We need to insert to the existing root
        TreeNode* node = make_treenode(data);
        TreeNode* temp = root;
        while (temp) {
            if (temp->is_leaf) {
                // Inserting at a leaf node
                if (temp->data > data) {
                    // Insert to the left
                    temp->left = node;
                    temp->is_leaf = 0;
                    break;
                }
                else {
                    // Insert to the right
                    temp->right = node;
                    temp->is_leaf = 0;
                    break;
                }
            }
            else {
                // Non leaf node
                if (temp->data > data) {
                    // Go to the left subtree
                    if (temp->left == NULL) {
                        // If the left subtree is empty, add it here
                        // and break, since we've finished insertion
                        temp->left = node;
                        break;
                    }
                    temp = temp->left;
                }
                else {
                    // Go to the right subtree
                    if (temp->right == NULL) {
                        // If the left subtree is empty, add it here
                        // and break, since we've finished insertion
                        temp->right = node;
                        break;
                    }
                    temp = temp->right;
                }
            }
        }
    }
    return root;
}

Now we’ve completed our insert procedure! Let’s now quickly complete the search_bst() function as well.

Searching a Binary Search Tree

This is very straightforward. We simply move to the left/right sub-trees based on the key comparison. We stop if we either reach a NULL node, or if the current root node key matches our target.

int search_bst(TreeNode* root, int target) {
    // Searches for target in the BST
    if (!root)
        return 0;
    if (root->data == target)
        return 1;
    else if (root->data > target)
        return search_bst(root->left, target);
    else
        return search_bst(root->right, target);
    return 0;
}

Now that we’ve implemented both insert and search, let’s test if our program works correctly as of now.

I’ll post the complete code until now, with additional functions for printing the BST in an in-order traversal.

/**
    Code for https://journaldev.com article
    Purpose: A Binary Search Tree Implementation
    @author: Vijay Ramachandran
    @date: 08-03-2020
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    // TreeNode structure for the Binary Search Tree (BST)
    // A BST has the left subtree being less than the root,
    // while the right subtree is greater than the root
    int data; // A Node contains data
    struct TreeNode* left, *right; // As well as pointers to the left and right children
    int is_leaf; // Check whether a node is a leaf node or not
}TreeNode;

TreeNode* make_treenode(int data) {
    // Construct a treenode pointer using data
    TreeNode* node = (TreeNode*) calloc (1, sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    node->is_leaf = 1;
    return node;
}

TreeNode* insert_bst(TreeNode* root, int data) {
    // Inserts data into it's appropriate position
    // in the BST
    if (!root) {
        // Make the root node
        root = make_treenode(data);
        return root;
    }
    else {
        // We need to insert to the existing root
        TreeNode* node = make_treenode(data);
        TreeNode* temp = root;
        while (temp) {
            if (temp->is_leaf) {
                // Inserting at a leaf node
                if (temp->data > data) {
                    // Insert to the left
                    temp->left = node;
                    temp->is_leaf = 0;
                    break;
                }
                else {
                    // Insert to the right
                    temp->right = node;
                    temp->is_leaf = 0;
                    break;
                }
            }
            else {
                // Non leaf node
                if (temp->data > data) {
                    // Go to the left subtree
                    if (temp->left == NULL) {
                        // If the left subtree is empty, add it here
                        // and break, since we've finished insertion
                        temp->left = node;
                        break;
                    }
                    temp = temp->left;
                }
                else {
                    // Go to the right subtree
                    if (temp->right == NULL) {
                        // If the left subtree is empty, add it here
                        // and break, since we've finished insertion
                        temp->right = node;
                        break;
                    }
                    temp = temp->right;
                }
            }
        }
    }
    return root;
}

int search_bst(TreeNode* root, int target) {
    // Searches for target in the BST
    if (!root)
        return 0;
    if (root->data == target)
        return 1;
    else if (root->data > target)
        return search_bst(root->left, target);
    else
        return search_bst(root->right, target);
    return 0;
}

void free_bst(TreeNode* root) {
    // Frees the complete BST from memory
    if (!root)
        return;
    free_bst(root->left);
    free_bst(root->right);
    free(root);
}

void print_search(TreeNode* root, int target) {
    if (search_bst(root, target) == 1) {
        printf("Value: %d found in the BST!\n", target);
    }
    else {
        printf("Value: %d is not found in the BST.\n", target);
    }
}

void print_bst(TreeNode* root) {
    // Prints the BST in an inorder traversal
    if (!root)
        return;
    print_bst(root->left);
    printf("Node: %d -> ", root->data);
    print_bst(root->right);
}


int main() {
    // Driver function for performing Binary Search Tree
    // operations
    TreeNode* root = make_treenode(45);
    root = insert_bst(root, 20);
    root = insert_bst(root, 15);
    root = insert_bst(root, 60);
    root = insert_bst(root, 40);
    root = insert_bst(root, 50);
    root = insert_bst(root, 70);
    print_bst(root);
    printf("\n");
    print_search(root, 15);
    print_search(root, 70);
    print_search(root, 35);
    free_bst(root);
    return 0;
}

Output

Node: 15 -> Node: 20 -> Node: 40 -> Node: 45 -> Node: 50 -> Node: 60 -> Node: 70 -> 
Value: 15 found in the BST!
Value: 70 found in the BST!
Value: 35 is not found in the BST.

Alright! This seems to work as expected, and we do get the sorted list of elements by in-order traversal.

Let’s now move onto the delete method.

Delete from a Binary Search Tree

This one is a bit more tricky compared to the rest. Since the iterative version is less intuitive, we’ll present a recursive algorithm for this.

We have multiple cases for deletion. The below algorithm is the most commonly used version for deletion from a BST.

  • If a node has no children, simply delete it from the tree.
  • Else, it has one child, remove the node and replace with its child. It doesn’t matter if it is the left or the right child.
  • If it has 2 children, this case is a bit more tricky. Here, we don’t delete this node. Rather, we find the in-order successor of that node and remove that node instead, after copying the key to the current node.

The in-order successor of a node is the next node that comes after in the in-order traversal.

For example, the in-order successor of the root node (45), is the node 50, since it is the next node that is greater than it.

Since it is the next node in the sorted order, it is the leftmost node in the right sub-tree of the node!

TreeNode* get_inorder_successor(TreeNode* node) {
    // Returns the inorder successor of the current node
    // But this is simply the leftmost node in the right subtree!
    // Assume that the right subtree of node exists
    TreeNode* temp = node->right;
    while(temp->left) {
        temp = temp->left;
    }
    return temp;
}

This method will return the in-order successor of a node in a tree, assuming that a right sub-tree exists.

Now, we can write our delete_bst() method, using the above algorithm. The code is shown below.

TreeNode* delete_bst(TreeNode* root, int target) {
    // Deletes the node corresponding to target, from the BST
    if (!root)
        return root;
    else {
        TreeNode* temp = root;
        if (temp->data > target) {
            // Search in the left subtree and delete there
            root->left = delete_bst(root->left, target);
        }
        else if (temp->data < target) {
            // Search in the right subtree and delete there
            root->right = delete_bst(root->right, target);
        }
        else {
            // We've found the node
            if (temp->left == NULL) {
                // No problem, as the left subtree is NULL
                // Update the node to it's right subtree
                // Even if it does not exist, it is the same!
                // We simply need to free the temp node
                TreeNode* del_node = temp;
                temp = temp->right;
                del_node->right = NULL;
                free(del_node);
                return temp;
            }
            else if (temp->right == NULL) {
                // If the right subtree is NULL, take the same
                // logic for the previous case
                TreeNode* del_node = temp;
                temp = temp->left;
                del_node->left = NULL;
                free(del_node);
                return temp;
            }
            else {
                // This node has two children. We need to find the inorder
                // successor and copy the data to the current node.
                TreeNode* inorder_successor = get_inorder_successor(temp);
                temp->data = inorder_successor->data;
                // Remove the inorder_successor node, since we've copied it's data
                // to the current node
                root->right = delete_bst(root->right, inorder_successor->data);
            }
        }
        return root;
    }
}

We’ve implemented our delete_bst() method as well! So, I’ll now post the complete code below.

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    // TreeNode structure for the Binary Search Tree (BST)
    // A BST has the left subtree being less than the root,
    // while the right subtree is greater than the root
    int data; // A Node contains data
    struct TreeNode* left, *right; // As well as pointers to the left and right children
    int is_leaf; // Check whether a node is a leaf node or not
}TreeNode;

TreeNode* make_treenode(int data) {
    // Construct a treenode pointer using data
    TreeNode* node = (TreeNode*) calloc (1, sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    node->is_leaf = 1;
    return node;
}

TreeNode* insert_bst(TreeNode* root, int data) {
    // Inserts data into it's appropriate position
    // in the BST
    if (!root) {
        // Make the root node
        root = make_treenode(data);
        return root;
    }
    else {
        // We need to insert to the existing root
        TreeNode* node = make_treenode(data);
        TreeNode* temp = root;
        while (temp) {
            if (temp->is_leaf) {
                // Inserting at a leaf node
                if (temp->data > data) {
                    // Insert to the left
                    temp->left = node;
                    temp->is_leaf = 0;
                    break;
                }
                else {
                    // Insert to the right
                    temp->right = node;
                    temp->is_leaf = 0;
                    break;
                }
            }
            else {
                // Non leaf node
                if (temp->data > data) {
                    // Go to the left subtree
                    if (temp->left == NULL) {
                        // If the left subtree is empty, add it here
                        // and break, since we've finished insertion
                        temp->left = node;
                        break;
                    }
                    temp = temp->left;
                }
                else {
                    // Go to the right subtree
                    if (temp->right == NULL) {
                        // If the left subtree is empty, add it here
                        // and break, since we've finished insertion
                        temp->right = node;
                        break;
                    }
                    temp = temp->right;
                }
            }
        }
    }
    return root;
}

int search_bst(TreeNode* root, int target) {
    // Searches for target in the BST
    if (!root)
        return 0;
    if (root->data == target)
        return 1;
    else if (root->data > target)
        return search_bst(root->left, target);
    else
        return search_bst(root->right, target);
    return 0;
}

TreeNode* get_inorder_successor(TreeNode* node) {
    // Returns the inorder successor of the current node
    // But this is simply the leftmost node in the right subtree!
    // Assume that the right subtree of node exists
    TreeNode* temp = node->right;
    while(temp->left) {
        temp = temp->left;
    }
    return temp;
}

TreeNode* delete_bst(TreeNode* root, int target) {
    // Deletes the node corresponding to target, from the BST
    if (!root)
        return root;
    else {
        TreeNode* temp = root;
        if (temp->data > target) {
            // Search in the left subtree and delete there
            root->left = delete_bst(root->left, target);
        }
        else if (temp->data < target) {
            // Search in the right subtree and delete there
            root->right = delete_bst(root->right, target);
        }
        else {
            // We've found the node
            if (temp->left == NULL) {
                // No problem, as the left subtree is NULL
                // Update the node to it's right subtree
                // Even if it does not exist, it is the same!
                // We simply need to free the temp node
                TreeNode* del_node = temp;
                temp = temp->right;
                del_node->right = NULL;
                free(del_node);
                return temp;
            }
            else if (temp->right == NULL) {
                // If the right subtree is NULL, take the same
                // logic for the previous case
                TreeNode* del_node = temp;
                temp = temp->left;
                del_node->left = NULL;
                free(del_node);
                return temp;
            }
            else {
                // This node has two children. We need to find the inorder
                // successor and copy the data to the current node.
                TreeNode* inorder_successor = get_inorder_successor(temp);
                temp->data = inorder_successor->data;
                // Remove the inorder_successor node, since we've copied it's data
                // to the current node
                root->right = delete_bst(root->right, inorder_successor->data);
            }
        }
        return root;
    }
}

void free_bst(TreeNode* root) {
    // Frees the complete BST from memory
    if (!root)
        return;
    free_bst(root->left);
    free_bst(root->right);
    free(root);
}

void print_search(TreeNode* root, int target) {
    if (search_bst(root, target) == 1) {
        printf("Value: %d found in the BST!\n", target);
    }
    else {
        printf("Value: %d is not found in the BST.\n", target);
    }
}

void print_bst(TreeNode* root) {
    // Prints the BST in an inorder traversal
    if (!root)
        return;
    print_bst(root->left);
    printf("Node: %d -> ", root->data);
    print_bst(root->right);
}

int main() {
    // Driver function for performing Binary Search Tree
    // operations
    TreeNode* root = make_treenode(45);
    root = insert_bst(root, 20);
    root = insert_bst(root, 15);
    root = insert_bst(root, 60);
    root = insert_bst(root, 40);
    root = insert_bst(root, 50);
    root = insert_bst(root, 70);
    print_bst(root);
    printf("\n");
    print_search(root, 15);
    print_search(root, 70);
    print_search(root, 35);
    root = delete_bst(root, 50);
    printf("Deleted 50 from the BST\n");
    print_bst(root);
    printf("\n");
    root = delete_bst(root, 45);
    printf("Deleted 45 from the BST\n");
    print_bst(root);
    printf("\n");
    free_bst(root);
    return 0;
}

Output

Node: 15 -> Node: 20 -> Node: 40 -> Node: 45 -> Node: 50 -> Node: 60 -> Node: 70 -> 
Value: 15 found in the BST!
Value: 70 found in the BST!
Value: 35 is not found in the BST.
Deleted 50 from the BST
Node: 15 -> Node: 20 -> Node: 40 -> Node: 45 -> Node: 60 -> Node: 70 -> 
Deleted 45 from the BST
Node: 15 -> Node: 20 -> Node: 40 -> Node: 60 -> Node: 70 -> 

Hooray! This seems to work as expected, after deleting 50 and 45. We’ve finally completed all our procedures, and we’re done!


Time Complexity of Implementation

The time complexity of the main procedures are given in the below table

ProcedureTime Complexity of Implementation
insert_bst()O(h) -> h is the height of the BST
search_bst()O(h) -> h is the height of the BST
delete_bstO(h) -> h is the height of the BST

The disadvantage of using BSTs

The problem with BSTs is that since the insertion can happen arbitrarily, the tree can become skewed, with the height of the BST being potentially proportional to the number of elements!

So now, the insert, search, and delete operations are equivalent to O(n) in the absolute worst case, instead of the expected O(logn)

Skewed Bst
Skewed Bst

To avoid this problem, some modifications to the BST model were proposed, and a popular data structure is called the AVL Tree. We’ll give you more details in our upcoming article, so stay tuned!


Download the Code

You can get the code through a Github Gist that I’ve uploaded. Feel free to ask any questions or provide suggestions in the comment section below!

Conclusion

Hopefully, you’ve learned how you can implement the methods for inserting, search and deleting into a Binary Search Tree in C/C++.

Our next article on this series will focus on AVL Trees, which aims to eliminate the problem of encountering a skewed tree, so stay tuned!

References


Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages