Binary Search Tree in C/C++ With Examples [Latest]

Oct 23, 2022

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.

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

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

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

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.

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.

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.

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

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

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:

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.

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`.

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.

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.

Output

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!

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.

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

Output

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

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)

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!

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!