Binary Search Tree in Data Structures

Binary Search Tree in Data Structure: An Overview

What is a binary search tree in data structure?

Properties of Binary Search Tree

1. Each node in the tree has at most two children, referred to as the left child and the right child.
2. The keys in the left subtree of a node are less than the keys in the node.
3. The keys in the right subtree of a node are greater than the key in the node.
4. The left and right subtrees themselves are also binary search trees.
5. The keys in a binary search tree are unique.

Binary search tree operations

Insertion

Algorithm

1. Start at the root of the tree.
2. If the tree is empty, create a new node and make it the root.
3. If the value of the new node is less than the value of the current node, move to the left child of the current node.
4. If the value of the new node is greater than the value of the current node, move to the right child of the current node.
5. Repeat steps 3 and 4 until a leaf node is reached.

 class Node:
     def __init__(self, value):
         self.value = value
         self.left = None
         self.right = None
 # Function to insert a new node in the binary search tree
 def insertNode(root, value):
     if root is None:
         root = Node(value)
         return root
     if value < root.value:
         root.left = insertNode(root.left, value)
     else:
         root.right = insertNode(root.right, value)
     return root
 # Function to print the binary search tree in inorder traversal
 def printInorder(root):
     if root is None:
         return
     printInorder(root.left)
     print(root.value, end=' ')
     printInorder(root.right)
 root = None
 n = int(input("Enter the number of nodes: "))
 for i in range(n):
     value = int(input("Enter the value of node {}: ".format(i+1)))
     root = insertNode(root, value)
 print("The binary search tree in inorder traversal:", end=' ')
 printInorder(root)

 import java.util.Scanner;
 class Node {
     int value;
     Node left;
     Node right;
 }
 public class Main {
     // Function to create a new node
     public static Node createNode(int value) {
         Node newNode = new Node();
         newNode.value = value;
         newNode.left = null;
         newNode.right = null;
         return newNode;
     }
     // Function to insert a new node in the binary search tree
     public static Node insertNode(Node root, int value) {
         if (root == null) {
             root = createNode(value);
             return root;
         }
         if (value < root.value) {
             root.left = insertNode(root.left, value);
         } else {
             root.right = insertNode(root.right, value);
         }
         return root;
     }
     // Function to print the binary search tree in inorder traversal
     public static void printInorder(Node root) {
         if (root == null) {
             return;
         }
         printInorder(root.left);
         System.out.print(root.value + " ");
         printInorder(root.right);
     }
     public static void main(String[] args) {
         Node root = null;
         Scanner sc = new Scanner(System.in);
         System.out.print("Enter the number of nodes: ");
         int n = sc.nextInt();
         for (int i = 0; i < n; i++) {
             System.out.print("Enter the value of node " + (i+1) + ": ");
             int value = sc.nextInt();
             root = insertNode(root, value);
         }
         System.out.print("The binary search tree in inorder traversal: ");
         printInorder(root);
     }
 }

 #include <iostream>
 using namespace std;
 struct Node {
     int value;
     Node* left;
     Node* right;
 };
 // Function to create a new node
 Node* createNode(int value) {
     Node* newNode = new Node;
     newNode->value = value;
     newNode->left = nullptr;
     newNode->right = nullptr;
     return newNode;
 }
 // Function to insert a new node in the binary search tree
 Node* insertNode(Node* root, int value) {
     if (root == nullptr) {
         root = createNode(value);
         return root;
     }
     if (value < root->value) {
         root->left = insertNode(root->left, value);
     }
     else {
         root->right = insertNode(root->right, value);
     }
     return root;
 }
 // Function to print the binary search tree in inorder traversal
 void printInorder(Node* root) {
     if (root == nullptr) {
         return;
     }
     printInorder(root->left);
     cout << root->value << " ";
     printInorder(root->right);
 }
 int main() {
     Node* root = nullptr;
     int n, value;
     cout << "Enter the number of nodes: ";
     cin >> n;
     for (int i = 0; i < n; i++) {
         cout << "Enter the value of node " << i + 1 << ": ";
         cin >> value;
         root = insertNode(root, value);
     }
     cout << "The binary search tree in inorder traversal: ";
     printInorder(root);
     return 0;
 }

 Enter the number of nodes: 5
Enter the value of node 1: 3
Enter the value of node 2: 1
Enter the value of node 3: 4
Enter the value of node 4: 2
Enter the value of node 5: 5
The binary search tree in inorder traversal: 1 2 3 4 5

Search

Algorithm

1. Start from the root node.
2. If the root node is null, the tree is empty, and the search is unsuccessful.
3. If the search value is equal to the value of the current node, return the current node.
4. If the search value is less than the value of the current node, go to the left child node.
5. If the search value is greater than the value of the current node, go to the right child node.
6. Repeat steps 3 to 5 until the search value is found or the current node is null.
7. If the search value is not found, return null.
   • Python
   • Java
   • C++

   
    class Node:
       def __init__(self, data):
           self.data = data
           self.left = None
           self.right = None
   def search(root, key):
       if root is None or root.data == key:
           return root
       if root.data < key:
           return search(root.right, key)
       return search(root.left, key)
   root = Node(50)
   root.left = Node(30)
   root.right = Node(70)
   root.left.left = Node(20)
   root.left.right = Node(40)
   root.right.left = Node(60)
   root.right.right = Node(80)
   key = 60
   result = search(root, key)
   if result is not None:
       print("Found:", result.data)
   else:
       print("Not found")

   
    class Node {
        int data;
        Node left;
        Node right;
        public Node(int data) {
            this.data = data;
            left = null;
            right = null;
        }
    }
    public class Main {
        static Node newNode(int data) {
            Node node = new Node(data);
            return node;
        }
        static Node search(Node root, int key) {
            if (root == null || root.data == key)
                return root;
            if (root.data < key)
                return search(root.right, key);
            return search(root.left, key);
        }
        public static void main(String[] args) {
            Node root = newNode(50);
            root.left = newNode(30);
            root.right = newNode(70);
            root.left.left = newNode(20);
            root.left.right = newNode(40);
            root.right.left = newNode(60);
            root.right.right = newNode(80);
            int key = 60;
            Node result = search(root, key);
            if (result != null)
                System.out.println("Found: " + result.data);
            else
                System.out.println("Not found");
        }
    }

   
               #include <iostream>
    using namespace std;
    struct Node {
        int data;
        Node* left;
        Node* right;
    };
    Node* newNode(int data) {
        Node* node = new Node();
        node->data = data;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    Node* search(Node* root, int key) {
        if (root == NULL || root->data == key)
            return root;
        if (root->data < key)
            return search(root->right, key);
        return search(root->left, key);
    }
    int main() {
        Node* root = newNode(50);
        root->left = newNode(30);
        root->right = newNode(70);
        root->left->left = newNode(20);
        root->left->right = newNode(40);
        root->right->left = newNode(60);
        root->right->right = newNode(80);
        int key = 60;
        Node* result = search(root, key);
        if (result != NULL)
            cout << "Found: " << result->data << endl;
        else
            cout << "Not found" << endl;
        return 0;
    }

   Output

    Found: 60

   Deletion

   To delete an element from a BST, the user first search for the element using the search operation. If the element is found, there are three cases to consider:

   Algorithm

   1. The node to be deleted has no children: In this case, simply remove the node from the tree.
   2. The node to be deleted has one child: In this case, remove the node from the tree and replace it with its child.
   3. The node to be deleted has two children: In this case, find the minimum value node in the right subtree (or the maximum value node in the left subtree) and replace the node to be deleted with this node. Then delete the minimum (or maximum) value node from the subtree.
      • Python
      • Java
      • C++

      
       # BST node class
       class Node:
           def __init__(self, key):
               self.key = key
               self.left = None
               self.right = None
       # Function to delete a node from BST
       def deleteNode(root, key):
           # Base case
           if root is None:
               return root
           # If the key to be deleted is smaller than the root's key,
           # then it lies in the left subtree
           if key < root.key:
               root.left = deleteNode(root.left, key)
           # If the key to be deleted is greater than the root's key,
           # then it lies in the right subtree
           elif key > root.key:
               root.right = deleteNode(root.right, key)
           # If key is same as root's key, then this is the node to be deleted
           else:
               # Node with only one child or no child
               if root.left is None:
                   temp = root.right
                   del root
                   return temp
               elif root.right is None:
                   temp = root.left
                   del root
                   return temp
               # Node with two children: Get the inorder successor (smallest in the right subtree)
               temp = root.right
               while temp.left is not None:
                   temp = temp.left
               # Copy the inorder successor's content to this node
               root.key = temp.key
               # Delete the inorder successor
               root.right = deleteNode(root.right, temp.key)
           return root
       # Function to insert a node into BST
       def insertNode(root, key):
           if root is None:
               return Node(key)
           if key < root.key:
               root.left = insertNode(root.left, key)
           else:
               root.right = insertNode(root.right, key)
           return root
       # Function to print inorder traversal of BST
       def inorderTraversal(root):
           if root is not None:
               inorderTraversal(root.left)
               print(root.key, end=" ")
               inorderTraversal(root.right)
       # Driver code
       if __name__ == "__main__":
           root = None
           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("Inorder traversal of the original tree:", end=" ")
           inorderTraversal(root)
           print()
           root = deleteNode(root, 20)
           print("Inorder traversal after deleting 20:", end=" ")
           inorderTraversal(root)
           print()
           root = deleteNode(root, 30)
           print("Inorder traversal after deleting 30:", end=" ")
           inorderTraversal(root)
           print()
           root = deleteNode(root, 50)
           print("Inorder traversal after deleting 50:", end=" ")
           inorderTraversal(root)
           print()

      
       class Node {
           int key;
           Node left, right;
           Node(int data) {
               key = data;
               left = right = null;
           }
       }
       class BST {
           // Function to delete a node from BST
           public static Node deleteNode(Node root, int key) {
               // Base case
               if (root == null) {
                   return root;
               }
               // If the key to be deleted is smaller than the root's key,
               // then it lies in the left subtree
               if (key < root.key) {
                   root.left = deleteNode(root.left, key);
               }
               // If the key to be deleted is greater than the root's key,
               // then it lies in the right subtree
               else if (key > root.key) {
                   root.right = deleteNode(root.right, key);
               }
               // If key is same as root's key, then this is the node to be deleted
               else {
                   // Node with only one child or no child
                   if (root.left == null) {
                       Node temp = root.right;
                       root = null;
                       return temp;
                   } else if (root.right == null) {
                       Node temp = root.left;
                       root = null;
                       return temp;
                   }
                   // Node with two children: Get the inorder successor (smallest in the right subtree)
                   Node temp = root.right;
                   while (temp.left != null) {
                       temp = temp.left;
                   }
                   // Copy the inorder successor's content to this node
                   root.key = temp.key;
                   // Delete the inorder successor
                   root.right = deleteNode(root.right, temp.key);
               }
               return root;
           }
           // Function to insert a node into BST
           public static Node insertNode(Node root, int key) {
               if (root == null) {
                   return new Node(key);
               }
               if (key < root.key) {
                   root.left = insertNode(root.left, key);
               } else {
                   root.right = insertNode(root.right, key);
               }
               return root;
           }
           // Function to print inorder traversal of BST
           public static void inorderTraversal(Node root) {
               if (root != null) {
                   inorderTraversal(root.left);
                   System.out.print(root.key + " ");
                   inorderTraversal(root.right);
               }
           }
           // Driver code
           public static void main(String[] args) {
               Node root = null;
               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);
               System.out.print("Inorder traversal of the original tree: ");
               inorderTraversal(root);
               System.out.println();
               root = deleteNode(root, 20);
               System.out.print("Inorder traversal after deleting 20: ");
               inorderTraversal(root);
               System.out.println();
               root = deleteNode(root, 30);
               System.out.print("Inorder traversal after deleting 30: ");
               inorderTraversal(root);
               System.out.println();
               root = deleteNode(root, 50);
               System.out.print("Inorder traversal after deleting 50: ");
               inorderTraversal(root);
               System.out.println();
           }
       }

      
       #include <iostream>
       using namespace std;
       // BST node structure
       struct Node {
           int key;
           Node* left;
           Node* right;
           Node(int data) {
               key = data;
               left = right = NULL;
           }
       };
       // Function to delete a node from BST
       Node* deleteNode(Node* root, int key) {
           // Base case
           if (root == NULL) {
               return root;
           }
           // If the key to be deleted is smaller than the root's key, 
           // then it lies in the left subtree
           if (key < root->key) {
               root->left = deleteNode(root->left, key);
           }
           // If the key to be deleted is greater than the root's key,
           // then it lies in the right subtree
           else if (key > root->key) {
               root->right = deleteNode(root->right, key);
           }
           // If key is same as root's key, then this is the node to be deleted
           else {
               // Node with only one child or no child
               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;
               }
               // Node with two children: Get the inorder successor (smallest in the right subtree)
               Node* temp = root->right;
               while (temp->left != NULL) {
                   temp = temp->left;
               }
               // Copy the inorder successor's content to this node
               root->key = temp->key;
               // Delete the inorder successor
               root->right = deleteNode(root->right, temp->key);
           }
           return root;
       }
       // Function to insert a node into BST
       Node* insertNode(Node* root, int key) {
           if (root == NULL) {
               return new Node(key);
           }
           if (key < root->key) {
               root->left = insertNode(root->left, key);
           }
           else {
               root->right = insertNode(root->right, key);
           }
           return root;
       }
       // Function to print inorder traversal of BST
       void inorderTraversal(Node* root) {
           if (root != NULL) {
               inorderTraversal(root->left);
               cout << root->key << " ";
               inorderTraversal(root->right);
           }
       }
       // Driver code
       int main() {
           Node* root = NULL;
           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);
           cout << "Inorder traversal of the original tree: ";
           inorderTraversal(root);
           cout << endl;
           root = deleteNode(root, 20);
           cout << "Inorder traversal after deleting 20: ";
           inorderTraversal(root);
           cout << endl;
           root = deleteNode(root, 30);
           cout << "Inorder traversal after deleting 30: ";
           inorderTraversal(root);
           cout << endl;
           root = deleteNode(root, 50);
           cout << "Inorder traversal after deleting 50: ";
           inorderTraversal(root);
           cout << endl;
           return 0;
       }

      Output

       Inorder traversal of the original tree: 20 30 40 50 60 70 80
      Inorder traversal after deleting 20: 30 40 50 60 70 80
      Inorder traversal after deleting 30: 40 50 60 70 80
      Inorder traversal after deleting 50: 40 60 70 80

   Traversal

   Traversal refers to the process of visiting all nodes in a BST. There are three types of traversal:
   • In-order traversal: In this traversal, the user visits the left subtree, then the root, and then the right subtree.

   Algorithm

   1. Traverse the left subtree in inorder.
   2. Visit the root node.
   3. Traverse the right subtree in inorder.
   • Pre-order traversal: In this traversal, the user visits the root, then the left subtree, and then the right subtree.

   Algorithm

   1. Visit the root node.
   2. Traverse the left subtree in preorder.
   3. Traverse the right subtree in preorder.
   • Post-order traversal: In this traversal, the user visits the left subtree, then the right subtree, and then the root.

   Algorithm

   1. Traverse the left subtree in postorder.
   2. Traverse the right subtree in postorder.
   3. Visit the root node.

   • Python
   • Java
   • C++

   # create an array
    class Node:
        def __init__(self, val):
            self.data = val
            self.left = None
            self.right = None
    def inorder(root):
        if root is None:
            return
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)
    def preorder(root):
        if root is None:
            return
        print(root.data, end=" ")
        preorder(root.left)
        preorder(root.right)
    def postorder(root):
        if root is None:
            return
        postorder(root.left)
        postorder(root.right)
        print(root.data, end=" ")
    if __name__ == "__main__":
        # Create a sample binary search tree
        root = Node(4)
        root.left = Node(2)
        root.right = Node(6)
        root.left.left = Node(1)
        root.left.right = Node(3)
        root.right.left = Node(5)
        root.right.right = Node(7)
        # Traversal operations
        print("Inorder traversal:", end=" ")
        inorder(root)
        print()
        print("Preorder traversal:", end=" ")
        preorder(root)
        print()
        print("Postorder traversal:", end=" ")
        postorder(root)
        print()

   
    class Node {
        int data;
        Node left, right;
        public Node(int val) {
            data = val;
            left = right = null;
        }
    }
    public class Main {
        // Inorder traversal
        static void inorder(Node root) {
            if (root == null) {
                return;
            }
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
        // Preorder traversal
        static void preorder(Node root) {
            if (root == null) {
                return;
            }
            System.out.print(root.data + " ");
            preorder(root.left);
            preorder(root.right);
        }
        // Postorder traversal
        static void postorder(Node root) {
            if (root == null) {
                return;
            }
            postorder(root.left);
            postorder(root.right);
            System.out.print(root.data + " ");
        }
        public static void main(String[] args) {
            // Create a sample binary search tree
            Node root = new Node(4);
            root.left = new Node(2);
            root.right = new Node(6);
            root.left.left = new Node(1);
            root.left.right = new Node(3);
            root.right.left = new Node(5);
            root.right.right = new Node(7);
            // Traversal operations
            System.out.print("Inorder traversal: ");
            inorder(root);
            System.out.println();
            System.out.print("Preorder traversal: ");
            preorder(root);
            System.out.println();
            System.out.print("Postorder traversal: ");
            postorder(root);
            System.out.println();
        }
    }

   
    #include <iostream>
    using namespace std;
    // Node structure
    struct Node {
        int data;
        Node* left;
        Node* right;
        Node(int val) {
            data = val;
            left = NULL;
            right = NULL;
        }
    };
    // Inorder traversal
    void inorder(Node* root) {
        if (root == NULL) {
            return;
        }
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
    // Preorder traversal
    void preorder(Node* root) {
        if (root == NULL) {
            return;
        }
        cout << root->data << " ";
        preorder(root->left);
        preorder(root->right);
    }
    // Postorder traversal
    void postorder(Node* root) {
        if (root == NULL) {
            return;
        }
        postorder(root->left);
        postorder(root->right);
        cout << root->data << " ";
    }
    int main() {
        // Create a sample binary search tree
        Node* root = new Node(4);
        root->left = new Node(2);
        root->right = new Node(6);
        root->left->left = new Node(1);
        root->left->right = new Node(3);
        root->right->left = new Node(5);
        root->right->right = new Node(7);
        // Traversal operations
        cout << "Inorder traversal: ";
        inorder(root);
        cout << endl;
        cout << "Preorder traversal: ";
        preorder(root);
        cout << endl;
        cout << "Postorder traversal: ";
        postorder(root);
        cout << endl;
        return 0;
    }

   Output

   Inorder traversal: 1 2 3 4 5 6 7 
   Preorder traversal: 4 2 1 3 6 5 7 
   Postorder traversal: 1 3 2 5 7 6 4 

   Advantages of binary search tree

   1. Efficient searching: One of the main advantages of BSTs is that they allow for very efficient searching of elements. Because of the way that data is stored in a BST, it is possible to search for an element in logarithmic time, which is much faster than searching through an unsorted array or list.
   2. Sorted order: Another advantage of BSTs is that the elements are automatically sorted in the tree structure. This can be useful for applications where the user needs to maintain an ordered list of elements.
   3. Easy to implement: BSTs are relatively easy to implement and can be built using simple recursive algorithms. This makes them a popular choice for developers who need to quickly implement data structures in their code.
   4. Dynamic size: Unlike some other data structures, such as arrays or linked lists, BSTs can be easily resized to accommodate new elements as they are added to the structure.
   5. Flexibility: BSTs can be used to implement a wide range of other data structures, such as sets, maps, and priority queues, making them a versatile choice for many different programming applications.

   Disadvantages of binary search tree

   1. Unbalanced trees: If a binary search tree is not properly balanced, its performance can become worse than O(log n) for searching and insertion operations, as these operations may need to traverse the entire height of the tree.
   2. Inefficient for large datasets: For very large datasets, BSTs may not be the best choice for storage and retrieval, as the tree height can become very large, and the space complexity of the tree can become an issue.
   3. Degenerate trees: A degenerate binary search tree is one in which each node has only one child, and the tree degenerates into a linked list. In such cases, searching and insertion operations can become O(n), which makes the BST less efficient than other data structures.
   4. Vulnerable to skewness: If the elements of a binary search tree are inserted in a specific order (such as already sorted), the tree may become skewed, with one branch becoming very long and the other very short, leading to unbalanced trees and affecting the performance.
   5. Inefficient for range queries: BSTs are not very efficient for range queries, as they require traversing the entire tree to find all nodes within a certain range, unlike other data structures such as B-trees or AVL trees.

   The complexity of the Binary Search tree (time and space complexity in data structure)

   Time Complexity of Binary search tree

   Operations	Best-case time complexity	Average case time complexity	Worst-case time complexity
   Insertion	O(log n)	O(log n)	O(n)
   Deletion	O(log n)	O(log n)	O(n)
   Search	O(log n)	O(log n)	O(n)

   Space complexity of binary search tree

   Operations	Space complexity
   Insertion	O(n)
   Deletion	O(n)
   Search	O(n)

   What are the Real-World Applications of Binary Search Trees?

   1. Databases: Many databases use BSTs to store and search for data. For example, MySQL and SQLite use BSTs to store indexes of the data they contain, making queries much faster.
   2. File Systems: File systems use BSTs to store and organize files on a hard drive. For example, the Windows NTFS file system uses BSTs to store the Master File Table (MFT), which contains information about all the files on the hard drive.
   3. Computer Networks: BSTs can be used to store routing tables in computer networks. This allows routers to quickly find the best route for a packet to take from one network to another.
   4. Sorting: BSTs can be used as a sorting algorithm. By inserting elements in a BST and then traversing it in order, the elements can be sorted in O(nlogn) time.
   5. Language Modeling: BSTs can be used to store n-grams in natural language processing tasks. This allows for efficient searching of the most common n-grams, making language modeling tasks faster.
   6. Machine Learning: BSTs can be used in decision tree-based machine learning algorithms, where the decision tree is a binary search tree that makes decisions based on the input features.
   7. Game Trees: BSTs can be used to represent game trees in game theory, allowing for efficient searching of possible game states and moves.

   Summary

   In conclusion, binary search trees are an incredibly useful tool in data structure and should not be overlooked. Using them efficiently is a skill all computer scientists should master. With enough practice, you too can interpret this complex construct with ease. Implementing the binary search tree properly allows you to maximize efficiency while searching through data structures far more quickly than other methods. Being aware of the ways you can explore your data through a binary search tree will give you an edge when dealing with complex information architectures. If you're looking for an efficient way to traverse through data structures, investing time in learning about binary search trees is certainly worth it! We hope this article has given you enough insight into the inner workings of a binary search tree in a data structure so that you can confidently make use of its capabilities!

Take our free skill tests to evaluate your skill!

In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.

GET TEST NOW