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
|
1 2 3 4 5 6 7 8 |
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.
|
1 2 3 4 5 6 7 8 |
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.
|
1 2 3 4 5 6 7 8 |
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.
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:
|
1 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
/** 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
|
1 2 3 4 |
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!
|
1 2 3 4 5 6 7 8 9 10 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 |
#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 BSTn"); print_bst(root); printf("n"); root = delete_bst(root, 45); printf("Deleted 45 from the BSTn"); print_bst(root); printf("n"); free_bst(root); return 0; } |
Output
|
1 2 3 4 5 6 7 8 |
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
| Procedure | Time 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_bst |
O(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)
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!