BUILD A BINARY SEARCH TREE

• 

  Implementation of Binary search tree using C++

BINARY SEARCH TREE

** The Inspiration behind the BST is built on the idea of the binary search algorithm, which allows for fast lookup, insertion and removal of nodes.

Binary Search Tree (or BST) is a special kind of binary tree in which the values of all the nodes of the left subtree of any node of the tree are smaller than the value of the node. Also, the values of all the nodes of the right subtree of any node are greater than the value of the node.

A binary Search Tree is a node-based binary tree data structure which has the following properties:
-> The left subtree of a node contains only nodes with keys lesser than the node’s key. -> The right subtree of a node contains only nodes with keys greater than the node’s key. -> The left and right subtree each must also be a binary search tree. -> There must be no duplicate nodes. **

Implementation of Binary search tree using C++

#include <iostream>  
using namespace std;  
struct Node {  
    int data;  
    Node *left;  
    Node *right;  
};  
Node* create(int item)  
{  
    Node* node = new Node;  
    node->data = item;  
    node->left = node->right = NULL;  
    return node;  
}  
/*Inorder traversal of the tree formed*/  
void inorder(Node *root)  
{  
    if (root == NULL)  
        return;  
    inorder(root->left); //traverse left subtree  
    cout<< root->data << "   "; //traverse root node  
    inorder(root->right); //traverse right subtree  
}  
Node* findMinimum(Node* cur) /*To find the inorder successor*/  
{  
    while(cur->left != NULL) {  
        cur = cur->left;  
    }  
    return cur;  
}  
Node* insertion(Node* root, int item) /*Insert a node*/  
{  
    if (root == NULL)  
        return create(item); /*return new node if tree is empty*/  
    if (item < root->data)  
        root->left = insertion(root->left, item);  
    else  
        root->right = insertion(root->right, item);  
    return root;  
}  
void search(Node* &cur, int item, Node* &parent)  
{  
    while (cur != NULL && cur->data != item)  
    {  
        parent = cur;  
        if (item < cur->data)  
            cur = cur->left;  
        else  
            cur = cur->right;  
    }  
}  
void deletion(Node*& root, int item) /*function to delete a node*/  
{  
    Node* parent = NULL;  
    Node* cur = root;  
    search(cur, item, parent); /*find the node to be deleted*/  
    if (cur == NULL)  
        return;  
    if (cur->left == NULL && cur->right == NULL) /*When node has no children*/  
    {  
        if (cur != root)  
        {  
            if (parent->left == cur)  
                parent->left = NULL;  
            else  
                parent->right = NULL;  
        }  
        else  
            root = NULL;  
        free(cur);       
    }  
    else if (cur->left && cur->right)  
    {  
        Node* succ  = findMinimum(cur->right);  
        int val = succ->data;  
        deletion(root, succ->data);  
        cur->data = val;  
    }  
    else  
    {  
        Node* child = (cur->left)? cur->left: cur->right;  
        if (cur != root)  
        {  
            if (cur == parent->left)  
                parent->left = child;  
            else  
                parent->right = child;  
        }  
        else  
            root = child;  
        free(cur);  
    }  
}  
int main()  
{  
  Node* root = NULL;  
  root = insertion(root, 45);  
  root = insertion(root, 30);  
  root = insertion(root, 50);  
  root = insertion(root, 25);  
  root = insertion(root, 35);  
  root = insertion(root, 45);  
  root = insertion(root, 60);  
  root = insertion(root, 4);  
  printf("The inorder traversal of the given binary tree is - \n");  
  inorder(root);  
  deletion(root, 25);  
  printf("\nAfter deleting node 25, the inorder traversal of the given binary tree is - \n");  
  inorder(root);   
  insertion(root, 2);  
  printf("\nAfter inserting node 2, the inorder traversal of the given binary tree is - \n");  
  inorder(root);  
  return 0;  
}  

Built With

• c++