C++ Program to Implement Binary Search Tree
The below program demonstrates all the major operations on a binary search tree: creation, searching, insertion and deletion.
// C++ Program to implement binary search tree
#include <iostream>
using namespace std;
// Node structure for a Binary Search Tree
struct Node {
int data;
Node* left;
Node* right;
};
// Function to create a new Node
Node* createNode(int data)
{
Node* newNode = new Node();
newNode->data = data;
newNode->left = newNode->right = nullptr;
return newNode;
}
// Function to insert a node in the BST
Node* insertNode(Node* root, int data)
{
if (root == nullptr) { // If the tree is empty, return a
// new node
return createNode(data);
}
// Otherwise, recur down the tree
if (data < root->data) {
root->left = insertNode(root->left, data);
}
else if (data > root->data) {
root->right = insertNode(root->right, data);
}
// return the (unchanged) node pointer
return root;
}
// Function to do inorder traversal of BST
void inorderTraversal(Node* root)
{
if (root != nullptr) {
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
}
// Function to search a given key in a given BST
Node* searchNode(Node* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == nullptr || root->data == key) {
return root;
}
// Key is greater than root's key
if (root->data < key) {
return searchNode(root->right, key);
}
// Key is smaller than root's key
return searchNode(root->left, key);
}
// Function to find the inorder successor
Node* minValueNode(Node* node)
{
Node* current = node;
// loop down to find the leftmost leaf
while (current && current->left != nullptr) {
current = current->left;
}
return current;
}
// Function to delete a node
Node* deleteNode(Node* root, int data)
{
if (root == nullptr)
return root;
// If the data to be deleted is smaller than the root's
// data, then it lies in the left subtree
if (data < root->data) {
root->left = deleteNode(root->left, data);
}
// If the data to be deleted is greater than the root's
// data, then it lies in the right subtree
else if (data > root->data) {
root->right = deleteNode(root->right, data);
}
// if data is same as root's data, then This is the node
// to be deleted
else {
// node with only one child or no child
if (root->left == nullptr) {
Node* temp = root->right;
delete root;
return temp;
}
else if (root->right == nullptr) {
Node* temp = root->left;
delete root;
return temp;
}
// node with two children: Get the inorder successor
// (smallest in the right subtree)
Node* temp = minValueNode(root->right);
// Copy the inorder successor's content to this node
root->data = temp->data;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Main function to demonstrate the operations of BST
int main()
{
Node* root = nullptr;
// create a BST
root = insertNode(root, 50);
root = insertNode(root, 30);
root = insertNode(root, 20);
root = insertNode(root, 40);
root = insertNode(root, 70);
root = insertNode(root, 60);
root = insertNode(root, 80);
// Print the inorder traversal of a BST
cout << "Inorder traversal of the given Binary Search "
"Tree is: ";
inorderTraversal(root);
cout << endl;
// delete a node in BST
root = deleteNode(root, 20);
cout << "After deletion of 20: ";
inorderTraversal(root);
cout << endl;
// Insert a node in BST
root = insertNode(root, 25);
cout << "After insertion of 25: ";
inorderTraversal(root);
cout << endl;
// Search a key in BST
Node* found = searchNode(root, 25);
// check if the key is found or not
if (found != nullptr) {
cout << "Node 25 found in the BST." << endl;
}
else {
cout << "Node 25 not found in the BST." << endl;
}
return 0;
}
Output
Inorder traversal of the given Binary Search Tree is: 20 30 40 50 60 70 80 After deletion of 20: 30 40 50 60 70 80 After insertion of 25: 25 30 40 50 60 70 80 Node 25 found in the BST.
Time Complexity:
Auxilliary Space:
The average time complexity for all three operations on BST is O (log n). In the worst case (Skewed BST) the time complexity can become O (n). n = number of nodes.The Space complexity for all three operations done on BST is O (1). This means no extra space or memory is required to perform these operations on a BST.
Binary Search Tree in C++
A Binary Search Tree (BST) is a type of binary tree in which the data is organized and stored in a sorted order. Unlike, a binary tree that doesn’t follow a specific order for node placement, in a binary search tree all the elements on the left side of a node are smaller than the node itself, and elements on the right side of a node are greater.
In this article, we will learn more about the binary search tree, operations performed on BST, and implementation of BST, as well as the advantages, disadvantages, and applications of binary search tree in C++.
Contact Us