In the previous article we studied about binary tree and traversals. You can read it by clicking this this. Binary Search Tree is a variation of binary tree where are few constraints the nodes should follow.
Properties of BST
For each node X, and its descendent(child) node y:
- If y is in left sub-tree then y.data <= x.data
- If y is in right sub-tree then y.data >= x.data
As you can see in the picture above, 30 left child of 50 because 30 < 50, and all sub-trees follow these properties.
BST Operations
Insertion to BST
Alright, now we have a better idea about binary search tree. Now, let's talk about how to insert an element to it. The main idea is to find a spot at the leaf node where there are no more branches below, and insert the new number there. This way, we ensure that the tree stays in order without breaking the properties of Binary Search Trees.
Let's implement the insertion operation in C++.
*Reading comment lines is essential to understand the code and try these codes yourself. If you are using a mobile phone to read this, make sure to rotate your screen while reading this code.
#include <iostream> // Including the input-output stream library for basic I/O operations
using namespace std; // Using the standard namespace to access standard library functions
// Define the structure of a node in the binary search tree
struct Node { // Declaration of a structure named Node
int data; // Integer data member to hold node's value
Node* left; // Pointer to the left child node
Node* right; // Pointer to the right child node
// Constructor to initialize a node
Node(int value) : data(value), left(nullptr), right(nullptr) {} // Constructor initializing data and setting left and right pointers to nullptr
};
// Function to insert a new node into the binary search tree
Node* insert(Node* root, int value) { // Function definition to insert a node into the binary search tree
// If the tree is empty, create a new node and make it the root
if (root == nullptr) { // If root is nullptr, indicating an empty tree
return new Node(value); // Create a new node with the given value and return its address
}
// If the value is less than the root's data, insert it into the left subtree
if (value < root->data) { // If the value to be inserted is less than the data of the current node
root->left = insert(root->left, value); // Recursively insert the value into the left subtree
}
// If the value is greater than or equal to the root's data, insert it into the right subtree
else { // If the value to be inserted is greater than or equal to the data of the current node
root->right = insert(root->right, value); // Recursively insert the value into the right subtree
}
return root; // Return the root of the modified subtree
}
// Function to print the inorder traversal of the binary search tree
void inorderTraversal(Node* root) { // Function definition to perform inorder traversal of the binary search tree
if (root != nullptr) { // If the current node is not nullptr
inorderTraversal(root->left); // Traverse the left subtree recursively
cout << root->data << " "; // Print the data of the current node
inorderTraversal(root->right); // Traverse the right subtree recursively
}
}
int main() { // Main function where the program execution begins
Node* root = nullptr; // Pointer to the root node initialized as nullptr
// Insert some elements into the binary search tree
root = insert(root, 50); // Inserting nodes into the binary search tree
insert(root, 30);
insert(root, 70);
insert(root, 80);
insert(root, 40);
insert(root, 10);
// Print the inorder traversal of the binary search tree
cout << "Inorder traversal of the binary search tree: ";
inorderTraversal(root); // Calling the function to perform inorder traversal
cout << endl;
return 0; // Indicates successful termination of the program
}
This is how it's done visually,
Step 01: root = insert(root, 50);
.png)
Step 02: insert(root, 30);
.png)
Step 03: insert(root, 70);
.png)
Step 04: insert(root, 80);
.png)
Step 05: insert(root, 40);
.png)
Step 06: insert(root, 10);
.png)
Deletion from BST
Now, you already know how to insert an element into a binary search tree. However, deletion is sometimes tricky. Deletion has 3 types of cases.
01.No Child: When deleting a node that has no children (e.g., in the tree above: 10, 40, 80), the node is simply removed.
02.One Child: When deleting a node that has one child (e.g., in the tree above: 70), the node is removed and its child takes its place.
03.Two Children: When deleting a node that has two children (e.g., in the tree above: 30, 50), replace the node with the smallest value from its right subtree, and then remove that smallest value.
Let's see our C++ implementation.
*Reading comment lines is essential to understand the code and try these codes yourself. If you are using a mobile phone to read this, make sure to rotate your screen while reading this code.
#include <iostream> // Include the input-output stream library
using namespace std; // Use the standard namespace
// Define the structure of a node in the binary search tree
struct Node {
int data; // Integer to store the data of the node
Node* left; // Pointer to the left child
Node* right; // Pointer to the right child
// Constructor to initialize a node
Node(int value) : data(value), left(nullptr), right(nullptr) {}
};
// Function to insert a new node into the binary search tree
Node* insert(Node* root, int value) {
// If the tree is empty, create a new node and make it the root
if (root == nullptr) {
return new Node(value);
}
// If the value is less than the root's data, insert it into the left subtree
if (value < root->data) {
root->left = insert(root->left, value);
}
// If the value is greater than or equal to the root's data, insert it into the right subtree
else {
root->right = insert(root->right, value);
}
return root; // Return the root of the modified tree
}
// Function to find the minimum value node in a given subtree
Node* findMin(Node* root) {
// Loop to find the leftmost leaf
while (root->left != nullptr) {
root = root->left;
}
return root; // Return the minimum node
}
// Function to delete a node from the binary search tree
Node* deleteNode(Node* root, int value) {
// If the tree is empty, return nullptr
if (root == nullptr) {
return root;
}
// If the value to be deleted is less than the root's data, go to the left subtree
if (value < root->data) {
root->left = deleteNode(root->left, value);
}
// If the value to be deleted is greater than the root's data, go to the right subtree
else if (value > root->data) {
root->right = deleteNode(root->right, value);
}
// If the value is the same as the root's data, this is the node to be deleted
else {
// Case 1: Node with no child (leaf node)
if (root->left == nullptr && root->right == nullptr) {
delete root; // Delete the node
return nullptr; // Return nullptr to the parent node
}
// Case 2: Node with only one child
else if (root->left == nullptr) {
Node* temp = root->right; // Store the right child
delete root; // Delete the current node
return temp; // Return the right child to the parent node
} else if (root->right == nullptr) {
Node* temp = root->left; // Store the left child
delete root; // Delete the current node
return temp; // Return the left child to the parent node
}
// Case 3: Node with two children
else {
Node* temp = findMin(root->right); // Find the inorder successor (minimum value in the right subtree)
root->data = temp->data; // Replace the current node's data with the inorder successor's data
root->right = deleteNode(root->right, temp->data); // Delete the inorder successor
}
}
return root; // Return the root of the modified subtree
}
// Function to print the inorder traversal of the binary search tree
void inorderTraversal(Node* root) {
if (root != nullptr) { // If the current node is not null
inorderTraversal(root->left); // Traverse the left subtree
cout << root->data << " "; // Print the data of the current node
inorderTraversal(root->right); // Traverse the right subtree
}
}
int main() {
Node* root = nullptr; // Initialize the root of the tree as null
// Insert some elements into the binary search tree
root = insert(root, 50); // Insert 50 into the tree and set as root
insert(root, 30); // Insert 30 into the tree
insert(root, 70); // Insert 70 into the tree
insert(root, 80); // Insert 80 into the tree
insert(root, 40); // Insert 40 into the tree
insert(root, 10); // Insert 10 into the tree
// Print the inorder traversal of the binary search tree
cout << "Inorder traversal of the binary search tree: ";
inorderTraversal(root); // Call inorderTraversal to print the tree
cout << endl; // Print a newline
// Delete a node from the binary search tree
root = deleteNode(root, 10); // Delete the node with value 10
cout << "Inorder traversal after deleting 10: ";
inorderTraversal(root); // Print the inorder traversal after deletion
cout << endl; // Print a newline
root = deleteNode(root, 70); // Delete the node with value 70
cout << "Inorder traversal after deleting 70: ";
inorderTraversal(root); // Print the inorder traversal after deletion
cout << endl; // Print a newline
root = deleteNode(root, 50); // Delete the node with value 50
cout << "Inorder traversal after deleting 50: ";
inorderTraversal(root); // Print the inorder traversal after deletion
cout << endl; // Print a newline
return 0; // End of the program
}
Here is a visualization of the deletion,
.png)
Step 01: deleteNode(root, 10);
.png)
.png)
Step 03: deleteNode(root, 50);
.png)
Traversal in BST
We learned about tree traversal in Binary Tree article. Binary Search Tree traversal follows the same method, so I won't explain it again. You can read about it by clicking the above link. However, if we use In-Order traversal, it returns the keys in the BST in sorted order, as seen in the previous example.
Time Complexities
The Binary Search Tree is commonly used for searching purposes. Here are the time complexities for different scenarios.
Best Case - O(1) [If the element we are searching for is the root node]
Average Case - O(log n)
Worst Case - O(log n)
Important Links
These links are provided to you to enhance your understanding. In the first link, you can understand how to insert into a binary search tree and delete from it. In the second link, you can insert, delete, create, and also you can traverse through the BST. Therefore, please try them to get a proper understanding.
Link 2 - https://visualgo.net/en/bst
(All credits go to the original creators of these websites)
Conclusion
In this post, we discussed Binary Search Tree data structure. If you think this is valuable, please share this with your friends. Thank you for reading this and have a nice day!
