Binary Search Tree (BST)

Binary search tree (BST) is a binary tree which its elements positioned in special order

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:

In each BST all values(i.e key) in left sub tree are less than values the keys in the root.
In each BST all values(i.e key) in right sub tree are larger than values the keys in the root.
In each BST all values(i.e key) in left sub tree are less than values in right sub tree.
The left and right subtrees should be BST.

Visualization of Binary Search Tree (BST)

Visualization of Binary Search Tree

Operations on Binary Search Tree (BST)

Search (key, tree)

Search for key (element) in the tree. If key is found on some node of tree, return pointer to that node or true; otherwise, return false.

Insert (key, tree)

Insert a new node with value key into the tree such that the property of BST is maintained.

Delete (key, tree)

Delete a node with value key from the tree such that the property of BST is maintained.
Handle the different cases (leaf node, node with one child, node with two children).

FindMin (tree)

Find the minimum element from the given non-empty BST. It is found in the leftmost leaf node of the left subtree.

FindMax (tree)

Find the maximum element from the given non-empty BST. It is found in the rightmost leaf node of the right subtree.

Representation

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

Minimum and Maximum values in Binary Search Tree

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;
    }
}
}

# implementationOfBinarySearchTree.py
class Node:
 def __init__(self, key):
     self.left = None
     self.right = None
     self.val = key
     self.parent = None
     self.height = 1
class BinarySearchTree:
 def __init__(self):
     self.root = None

 def insert(self, key):
     if self.root is None:
         self.root = Node(key)
     else:
         self._insert(self.root, key)

 def _insert(self, root, key):
     if key < root.val:
         if root.left is None:
             root.left = Node(key)
             root.left.parent = root
         else:
             self._insert(root.left, key)
     else:
         if root.right is None:
             root.right = Node(key)
             root.right.parent = root
         else:
             self._insert(root.right, key)

 def search(self, key):
     return self._search(self.root, key)

 def _search(self, root, key):
     if root is None or root.val == key:
         return root
     if key < root.val:
         return self._search(root.left, key)
     return self._search(root.right, key)

 def find_min(self):
     return self._find_min(self.root)

 def _find_min(self, node):
     while node.left is not None:
         node = node.left
     return node

 def find_max(self):
     return self._find_max(self.root)

 def _find_max(self, node):
     while node.right is not None:
         node = node.right
     return node

 def delete(self, key):
     self.root = self._delete_node(self.root, key)

 def _delete_node(self, root, key):
     if not root:
         return root
     if key < root.val:
         root.left = self._delete_node(root.left, key)
     elif key > root.val:
         root.right = self._delete_node(root.right, key)
     else:
         if not root.left:
             return root.right
         elif not root.right:
             return root.left
         temp = self.find_min(root.right)
         root.val = temp.val
         root.right = self._delete_node(root.right, temp.val)
     return root
 def inorder_traversal(self, node):
     if node:
         self.inorder_traversal(node.left)
         print(node.val, end=' ')
         self.inorder_traversal(node.right)
 def print_tree(self):
     if self.root is not None:
         self.inorder_traversal(self.root)
     else:
         print("Tree is empty")

// implementationOfBinarySearchTree.js
class Node {
 constructor(data) {
     this.data = data;
     this.left = null;
     this.right = null;
 }
}
class BinarySearchTree {
 constructor() {
     this.root = null;
 }

 insert(data) {
     const newNode = new Node(data);
     if (this.root === null) {
         this.root = newNode;
     } else {
         this._insertNode(this.root, newNode);
     }
 }

 _insertNode(node, newNode) {
     if (newNode.data < node.data) {
         if (node.left === null) {
             node.left = newNode;
         } else {
             this._insertNode(node.left, newNode);
         }
     } else {
         if (node.right === null) {
             node.right = newNode;
         } else {
             this._insertNode(node.right, newNode);
         }
     }
 }

 search(data) {
     return this._searchNode(this.root, data);
 }

 _searchNode(node, data) {
     if (node === null || node.data === data) {
         return node;
     }
     if (data < node.data) {
         return this._searchNode(node.left, data);
     } else {
         return this._searchNode(node.right, data);
     }
 }

 findMin() {
     return this._findMinNode(this.root);
 }

 _findMinNode(node) {
     while (node && node.left !== null) {
         node = node.left;
     }
     return node;
 }

 findMax() {
     return this._findMaxNode(this.root);
 }

 _findMaxNode(node) {
     while (node && node.right !== null) {
         node = node.right;
     }
     return node;
 }

 delete(data) {
     this.root = this._deleteNode(this.root, data);
 }

 _deleteNode(node, data) {
     if (node === null) return null;

     if (data < node.data) {
         node.left = this._deleteNode(node.left, data);
     } else if (data > node.data) {
         node.right = this._deleteNode(node.right, data);
     } else {
         // Node with one child or no child
         if (node.left === null) return node.right;
         else if (node.right === null) return node.left;

         // Node with two children: Get the in-order successor
         const minRight = this._findMinNode(node.right);
         node.data = minRight.data;
         node.right = this._deleteNode(node.right, minRight.data);
     }
     return node;
 }

 inorderTraversal(node = this.root) {
     if (node !== null) {
         this.inorderTraversal(node.left);
         console.log(node.data);
         this.inorderTraversal(node.right);
     }
 }
}

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)

Binary Search Tree (BST)

On this page