# Implementing a Binary Search Tree (BST) in C++

#### Data Structures C++ Software Engineering tree data structure Problems on Binary Tree binary search tree

Sign up for FREE 1 month of Kindle and read all our books for free.

Get FREE domain for 1st year and build your brand new site

In this article, we have explained the idea of implementing Binary Search Tree (BST) from scratch in C++ including all basic operations like insertion, deletion and traversal.

Binary Search Tree is similar to a graph but with some special properties, a BST (Binary Search Tree) has a node, left pointer and a right pointer. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key.

Binary Search Tree, is a node-based binary tree data structure which has the following properties:

• The left subtree contains only nodes with data less than the root’s data.
• The right subtree contains only nodes with data greater than the root’s data.
• Duplicate nodes shouldn't exist in the tree.

The binary search tree has three operations:

• Searching
• Traversion
• Deletion

For the core functionality of C++ Standard template library, we include <bits/stdc++.h> header file and use std namespace.

#include <bits/stdc++.h>
using namespace std;


We define a binary tree with a Node which contains data and pointers to left and right Node of the tree.

//Creating a Tree Node class
class Node{
public:
int data;
Node* left;
Node* right;
Node(int d){
data = d;
left = NULL;
right = NULL;
}
}


Now we'll implement binary search tree functionalities like searching, inserting, travesing and deleting

### Searching for a key in binary tree:

We will create a function to search a given key in the binary tree with a starting node.

For searching a particular key we'll first compare the given element with the node->val , if the node->val is more than the key value, we'll search the left subtree from the given node. Similarly, we'll search the right subtree if the node->val is less than the key value.

Implementation:

Node* search(Node* root, int key) {
if(root == NULL || root->data == key)
return root;

// Key is greater than root's data
if(root->data < key)
return search(root->right,key);

// Key is smaller than root's data
return search(root->left,key);
}


### Inserting a key in the binary tree:

For insertion of the data in a binary tree we will create a function which returns Node pointer(Node*) and takes in two input parameters: root node and data for insertion.

To insert an element in binary search tree we'll compare the data we want to insert with the tree elements, if the node element's data is less than the data to be inserted, we'll move to the right subtree to find the position to insert. Similarly, if the node->data is more than the data to be inserted we'll move towards left subtree to find the position of insertion of element. If we find the correct position, we create a node with data as data to be inserted and push it into binary tree.

Implementation:

    Node* insert(Node* root, int data) {
if(root == NULL){
return new Node(data);
}
else{
Node* cur;
if(data <= root->data) {
cur = insert(root->left, data);
root->left = cur;
}
else {
cur = insert(root->right, data);
root->right = cur;
}
return root;
}
}


Visual Representation:

### Deleting a key in binary tree:

Deleting a node in binary search tree is similar to insertion, but when we find a node to be deleted, we also delete it's left and right subtree.

In deletion, there are two possibilities to check:

1. If the node to be deleted has children, then the combined system (node+leaves) gets deleted.
2. If the node to be deleted is the leaf, then only the leaf is deleted.

Implementation:

1. If node is leaf then delete the leaf.
    Node* deletenode(Node* root, int k)
{
// Base case
if (root == NULL)
return root;
//If root->data is greater than k then we delete the root's subtree
if(root->data > k){
root->left = deletenode(root->left, k);
return root;
}
else if(root->data < k){
root->right = deletenode(root->right, k);
return root;
}

// If one of the children is empty
if (root->left == NULL) {
Node* temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL) {
Node* temp = root->left;
delete root;
return temp;
}

1. If both children exist then we delete the node(Parent) + the children
else {
Node* Parent = root;
// Find successor of the node
Node *succ = root->right;
while (succ->left != NULL) {
Parent = succ;
succ = succ->left;
}

if (Parent != root)
Parent->left = succ->right;
else
Parent->right = succ->right;

// Copy Successor Data
root->data = succ->data;

// Delete Successor and return root
delete succ;
return root;
}
}


### Traversals in binary tree:

There are three types of traversals in binary tree:

• Inorder traversal : In this traversal, we first traverse the left subtree completely, then visit the node and in the end traverse the right subtree.

• Preorder traversal: In this traversal, we first visit the node, then traverse the right subtree completely and then the left subtree.

• Postorder traversal: In this traversal, we first traverse the left subtree then the right subtree and in the end visit the node.

Implementation of the algorithms:

• Inorder traversal:
    void inorder(Node* root){
if(root == NULL)
return;

//First recur on left subtree
inorder(root->left);
//Then read the data of child
cout << root->data << " ";
// Recur on the right subtree
inorder(root->right);
}

• Preorder traversal:
    void preorder(Node* root){
if(root == NULL)
return;

//First read the data of child
cout << root->data << " ";
//Then recur on left subtree
preorder(root->left);
//Then Recur on the right subtree
preorder(root->right);
}

• Postorder traversal:
    void postorder(Node* root){
if(root == NULL)
return;

//Then recur on left subtree
postorder(root->left);
//Then Recur on the right subtree
postorder(root->right);
//First read the data of child
cout << root->data << " ";
}


### Complete implementation of binary tree:

We can now implement a binary search tree in C++ using above functions:
Firstly, we'll include the header files which are necessary.

#include <bits/stdc++.h>
using namespace std;


Creating a Tree Node class

class Node{
public:
int data;
Node* left;
Node* right;
Node(int d){
data = d;
left = NULL;
right = NULL;
}


Then let's define a function to insert node in the tree.


Node* insert(Node* root, int data) {
if(root == NULL){
return new Node(data);
}
else{
Node* cur;
if(data <= root->data) {
cur = insert(root->left, data);
root->left = cur;
}
else {
cur = insert(root->right, data);
root->right = cur;
}
return root;
}
}


Also, defining the inorder traversal.

    //Indorder traversal
void inorder(Node* root){
if(root == NULL)
return;

inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}


Implementing the search function.

    //Searching function
Node* search(Node* root, int key) {
if(root == NULL || root->data == key)
return root;

// Key is greater than root's data
if(root->data < key)
return search(root->right,key);

// Key is smaller than root's data
return search(root->left,key);
}


Implementing deletenode function.

    Node* deletenode(Node* root, int k)
{
// Base case
if (root == NULL)
return root;
//If root->data is greater than k then we delete the root's subtree
if(root->data > k){
root->left = deletenode(root->left, k);
return root;
}
else if(root->data < k){
root->right = deletenode(root->right, k);
return root;
}

// If one of the children is empty
if (root->left == NULL) {
Node* temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL) {
Node* temp = root->left;
delete root;
return temp;
}
else {
Node* Parent = root;
// Find successor of the node
Node *succ = root->right;
while (succ->left != NULL) {
Parent = succ;
succ = succ->left;
}

if (Parent != root)
Parent->left = succ->right;
else
Parent->right = succ->right;

// Copy Successor Data
root->data = succ->data;

// Delete Successor and return root
delete succ;
return root;
}
}
};


Here the main() function starts, in which we'll initialize the Tree node with 0 and fill in the data necessary.

int main(){
Node Tree(0);
Node* root = NULL;
//Number of nodes to be inserted
int t;
cin>>t;
while(t--){
int data;
cin>>data;
root = Tree.insert(root,data);
}


Using levelOrder function defined in the Node class.

    //levelOrder
Tree.levelOrder(root);


Using search() function to find the required key value in the tree.

    //Searching data
cout << "Enter the data to find:";
int data;
cin>>data;
Node* find_element = Tree.search(root,data);


Using deletenode funtion to delete a node.

    int delete_data;
cin>>delete_data;
Node* deleteelement = Tree.deletenode(root,delete_data);
return 0;
}


Thank you for reading this article at OpenGenus and enhancing your knowledge!

#### Sahil Silare

B.Tech Student in Computer Science at National Institute of Technology (NIT), Raipur (2019 - 2023) | Intern at OpenGenus

Vote for Sahil Silare for Top Writers 2021: