Binary Search Tree (BST)

Introduction

A Binary Search Tree (BST) is a binary tree that is either empty or in which every node conatins a key (value) and satisfies the following conditions:

1. In each BST all values(i.e key) in left sub tree are less than values the keys in the root.

2. In each BST all values(i.e key) in right sub tree are larger than values the keys in the root.

3. In each BST all values(i.e key) in left sub tree are less than values in right sub tree.

4. The left and right subtrees should be BST.

Visualization of Binary Search Tree (BST)

Operations on Binary Search Tree (BST)

Representation

struct BST{
  int element,
  struct BST* left,
  struct BST* right,
}
struct BST *root = NULL // initially initilizing with NULL

1. Searching

In BST, Searching of the desired data item can be performed by branching into left or right subtree untill the desired data item is found.

Algorithm

Step 1: If the tree is empty or the element is the same as the element in the root, return the root.
Step 2: Else if the element is less than the root element, search for the element in the left subtree of the given tree recursively.
Step 3: Else, if the element is greater than the root element, search for the element in the right subtree of the given tree recursively.

Pseudocode

search(root, element){
  if(root == NULL or element == root->element){
    return root
  }else if(element < root-> element){
    search(root->left, element)
  }else{
    search(root->right, element)
  }
}

2. Insert

A new key is always inserted at the leaf by maintaining the property of the binary search tree. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.

Algorithm

Step 1: If the tree is empty, create a new node, store the data in it, and make this new node the root of the tree. Otherwise, compare the data to the data stored at the root.

Step 2: If the data is identical to the root, do not change the tree.

Step 3: If the data is smaller, insert the new item into the left subtree of the root recursively.

Step 4: If the data is greater, insert the new item into the right subtree of the root recursively.

Pseudocode

Node * insert(Node *root, int data){

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

  return root;
}

Deleteion

For Deleteion we consider a 3 case:

1

When the node is to be deleted may be a leaf node or has no child

• In this case simply delete a node and set NULL pointer to its parent node in those side in which this deleted node exist.

2

When the node is to be deleted has a single child

• In this case the child of the node is to be deleted is append with its parent node.

  

3

When the node is to be deleted as both child

• In this case the child of the node is to be deleted is replaced with inorder-successor node . OR The node to be deleted is either replaced by its right subtree of leftmost node or replaced by its left subtree of rightmost node.

  

Algorithm

Step 1: Start at the root node of the BST.
Step 2: Compare the value of the node to be deleted with the value of the root node.

Step 3: If the value of the node to be deleted is less than the value of the root node, go to the left subtree of the root node recursively.

Step 4: If the value of the node to be deleted is greater than the value of the root node, go to the right subtree of the root node recursively.

Step 5: If the value of the node to be deleted is equal to the value of the root node, perform the deletion operation.

Step 6: If the node to be deleted is a leaf node or has only one child, perform the deletion operation directly.

Step 7: If the node to be deleted has two children, find the minimum value in the right subtree to replace it with and perform the deletion operation.

Pseudocode

node* delete_node(node *root, int data)
{
 if(root == nullptr) return root;
 else if(data < root->data) root->left = delete_node(root->left, data);
 else if(data > root->data) root->right = delete_node(root->right, data);
 else
 {
 if(root->left == nullptr && root->right == nullptr) // Case 1
 {
 free(root);
 root = nullptr;
 }
 else if(root->left == nullptr) // Case 2
 {
 node* temp = root;
 root= root->right;
 free(temp);
 }
 else if(root->right == nullptr) // Case 2
 {
 node* temp = root;
 root = root->left;
 free(temp);
 }
 else // Case 3
 {
 node* temp = root->right;
 while(temp->left != nullptr) temp = temp->left;
 root->data = temp->data;
 root->right = delete_node(root->right, temp->data);
 }
 }
 return root;
}

FindMin :

The left subtree of a node contains nodes with keys smaller than the node's key, and the leftmost node has the minimum value. The leftmost node is a left node without a left child.

Algorithm

Traverse the node from root to left recursively until left is NULL.
The node whose left is NULL is the node with minimum value.

Pseudocode

int FindMin(struct node* node)  
{  
    struct node* current = node;  
    while (current->left != NULL)  
    {  
        current = current->left;  
    }  
    return(current->key);  
}  

FindMax :

The right subtree of a node contains nodes with keys greater than the node's key, and the rightmost node has the maxValue value. The rightmost node is a right node without a right child.

Algorithm

Traverse the node from root to right recursively until right is NULL.
The node whose right is NULL is the node with Maximum value.

Pseudocode

int FindMax(struct node* node)  
{  
    struct node* current = node;  
    while (current->right != NULL)  
    {  
        current = current->right;  
    }  
    return(current->key);  
}  

Coding Implementation

// implementationofbinarySearchTree.cpp

#include <iostream>
using namespace std;

struct BST
{
int data;
struct BST *left, *right;
};

struct BST *createNode(int element)
{
struct BST *newNode = new BST();
newNode->data = element;
newNode->left = newNode->right = NULL;
return newNode;
}

struct BST *Search(struct BST *root, int element)
{
if (root == NULL || element == root->data)
{
    return root;
}
else if (element < root->data)
{
    return Search(root->left, element);
}
else
{
    return Search(root->right, element);
}
}

struct BST *Insert(struct BST *root, int element)
{

if (root == NULL)
{
    return createNode(element);
}
else if (element < root->data)
{
    root->left = Insert(root->left, element);
}
else
{
    root->right = Insert(root->right, element);
}

return root;
}

struct BST *findMinNode(struct BST *root)
{
while (root->left != NULL)
{
    root = root->left;
}
return root;
}

struct BST *Delete(struct BST *root, int element)
{
if (root == NULL)
{
    return root;
}
else if (element < root->data)
{
    root->left = Delete(root->left, element);
}
else if (element > root->data)
{
    root->right = Delete(root->right, element);
}
else
{
    if (root->left == NULL)
    {
        struct BST *temp = root->right;
        delete root;
        return temp;
    }
    else if (root->right == NULL)
    {
        struct BST *temp = root->left;
        delete root;
        return temp;
    }
    else
    {
        struct BST *temp = findMinNode(root->right);
        root->data = temp->data;
        root->right = Delete(root->right, temp->data);
    }
    return root;
}
}

void findMin(struct BST *root)
{
if (root == NULL)
{
    cout << "Tree  is Empty." << endl;
    return;
}
struct BST *minNode = findMinNode(root);
cout << "Minimum data is: " << minNode->data << endl;
return;
}
void findMax(struct BST *root)
{
if (root == NULL)
{
    cout << "Tree is Empty." << endl;
    return;
}
while (root->right != NULL)
{
    root = root->right;
}
cout << "Maximum data is: " << root->data << endl;
return;
}

void inOrderTraversel(struct BST *root)
{
if (root == NULL)
    return;

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

int main()
{
struct BST *root = NULL;
int option, element;
struct BST *searchResult = NULL;

while (true)
{
    cout << "\nChoose an operation:\n";
    cout << "1. SEARCH\n2. INSERT\n3. DELETE\n4. FIND MIN\n5. FIND MAX\n6. INORDER TRAVERSAL\n7. EXIT\n";
    cout << "Enter your choice: ";
    cin >> option;

    switch (option)
    {
    case 1:
        cout << "Enter the element you want to search: ";
        cin >> element;
        searchResult = Search(root, element);
        if (searchResult == NULL)
            cout << element << " is not found in the tree." << endl;
        else
            cout << searchResult->data << " is found in the tree." << endl;
        break;

    case 2:
        cout << "Enter the element you want to insert: ";
        cin >> element;
        root = Insert(root, element);
        cout << element << " is inserted successfully." << endl;
        break;

    case 3:
        cout << "Enter the element to delete: ";
        cin >> element;
        root = Delete(root, element);
        if (root == NULL)
        {
            cout << element << " does not exist in the given tree." << endl;
        }
        else
        {
            cout << element << " is deleted successfully from the tree." << endl;
        }
        break;
    case 4:

        findMin(root);

        break;
    case 5:
        findMax(root);
        break;
    case 6:
        cout << "In-order traversal: ";
        inOrderTraversel(root);
        cout << endl;
        break;
    case 7:
        return 0;

    default:
        cout << "Invalid option! Try again." << endl;
        break;
    }
}
}

Properties of Binary Search Tree

1. Sorted order: The values in a BST are stored in a sorted order, making it easy to search for specific values.
2. Maximum and minimum values: The maximum value in a BST is the rightmost node, and the minimum value is the leftmost node.
3. Balanced tree: A balanced BST ensures that search, insertion, and deletion operations are performed in O(log n) time complexity on average.
4. Unique values: A BST can only have unique values in each node. This is because if there were two nodes with the same value, it would violate the binary search property.

Advantages of Binary Search Tree

1. Efficient searching: BSTs allow for efficient searching of data. Due to the sorted order of the tree, search operations can be performed in O(log n) time complexity on average.
2. Efficient insertion and deletion: When adding or removing a node from a BST, the tree is automatically rebalanced to maintain the binary search property.
3. Sorted order: The sorted order of a BST makes it easy to perform operations that require the data to be sorted, such as finding the maximum or minimum value, or performing in-order traversal.

Time Complexity

Time complexity O(log n)
The search space is reduced by half at each step.

Space Complexity

Storage Space: O(n)
Recursive Call Stack Space: O(log n) (balanced), O(n) (unbalanced)