Binary Search Tree in Data Structures

Binary Search Tree in Data Structures: An Overview

A binary search tree (BST) in Data Structures is a sorted binary tree, where we can easily search for any key using the binary search algorithm. We already have learned binary search, tree data structure, and binary tree. In this DSA tutorial, we will learn binary search trees, their operations, implementation, etc. To further enhance your understanding, consider enrolling in the best DSA training, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is a Binary Search Tree in Data Structures?

Binary Search Trees are special kinds of Binary Trees having some special characteristics. It is called a binary tree because each tree node has up to two children. It is called a search tree because it can be used to search a number in O(log(n)) time. The only difference between the idea of Binary Search and Binary Search Tree is that BST uses Binary Trees to represent the data set instead of an array.

Special Characteristics of Binary Search Tree

These properties differentiate a Binary Search tree from a Binary tree.

1. The keys of nodes in the left subtree of a node are less than the node’s key.
2. The keys of nodes in the right subtree of a node are greater than the node’s key.
3. Both subtrees of each node are also BSTs i.e. they have the above two features.

The binary tree on the right isn't a binary search tree because the right subtree of the node "3" contains a value smaller than it.

Read More: Data Structure Interview Questions and Answers

Standard Operations on Binary Search Trees

1. Search

To search in a binary search tree, we need to take care that each left subtree has values below the root and each right subtree has values above the root. If the value is below the root, the value is not in the right subtree; we need to only search in the left subtree and if the value is above the root, the value is not in the left subtree; we need to only search in the right subtree.

Algorithm for Search Operation in a Binary Search Tree

If root == NULL 
    return NULL;
If number == root->data 
    return root->data;
If number < root->data 
    return search(root->left)
If number > root->data 
    return search(root->right)

According to the 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.

If the value is found, we return the value so that it gets propagated in each recursion step as shown in the image below. If you might have noticed, we have called return search(struct node*) four times. When we return either the new node or NULL, the value gets returned again and again until the search(root) returns the final result.

If the value is not found, we eventually reach the left or right child of a leaf node which is NULL and it gets propagated and returned.

2. Insertion

To insert an element in a BST, we need to maintain the rule that the left subtree is lesser than the root, and the right subtree is larger than the root. We keep going to either the right subtree or the left subtree depending on the value and when we reach a point left or right subtree is null, we put the new node there.

Algorithm for Insertion Operation in a Binary Search Tree

If node == NULL 
    return createNode(data)
if (data < node->data)
    node->left  = insert(node->left, data);
else if (data > node->data)
    node->right = insert(node->right, data);  
return node;

According to the 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.

We have attached the node but we still have to exit from the function without doing any damage to the rest of the tree. This is where the return node; at the end comes in handy. In the case of NULL, the newly created node is returned and attached to the parent node, otherwise, the same node is returned without any change as we go up until we return to the root.

This makes sure that as we move back up the tree, the other node connections aren't changed.

3. Deletion

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

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 only one child: In this case, remove the child node from its original position and replace the node to be deleted with its child node.

   

   

   

3. The node to be deleted has two children: In this case, get the in-order successor of that node, replace the node with the inorder successor, and then remove the inorder successor from its original position.

   

   

   

Implementation of Binary Search Trees in Different Programming Languages

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

# Inorder traversal
def inorder(root):
    if root is not None:
        # Traverse left
        inorder(root.left)

        # Traverse root
        print(str(root.key) + "->", end=' ')

        # Traverse right
        inorder(root.right)


# Insert a node
def insert(node, key):

    # Return a new node if the tree is empty
    if node is None:
        return Node(key)

    # Traverse to the right place and insert the node
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    return node


# Find the inorder successor
def minValueNode(node):
    current = node

    # Find the leftmost leaf
    while(current.left is not None):
        current = current.left

    return current


# Deleting a node
def deleteNode(root, key):

    # Return if the tree is empty
    if root is None:
        return root

    # Find the node to be deleted
    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif(key > root.key):
        root.right = deleteNode(root.right, key)
    else:
        # If the node is with only one child or no child
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp

        # If the node has two children,
        # place the inorder successor in position of the node to be deleted
        temp = minValueNode(root.right)

        root.key = temp.key

        # Delete the inorder successor
        root.right = deleteNode(root.right, temp.key)

    return root


root = None
root = insert(root, 9)
root = insert(root, 3)
root = insert(root, 2)
root = insert(root, 4)
root = insert(root, 7)
root = insert(root, 10)
root = insert(root, 15)
root = insert(root, 5)

print("Inorder traversal: ", end=' ')
inorder(root)

print("\nDelete 10")
root = deleteNode(root, 10)

print("Inorder traversal: ", end=' ')
inorder(root)
    

class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;

    BinaryTree() {
        root = null;
    }

    // Inorder traversal
    void inorder(Node root) {
        if (root != null) {
            // Traverse left
            inorder(root.left);

            // Traverse root
            System.out.print(root.key + "-> ");

            // Traverse right
            inorder(root.right);
        }
    }

    // Insert a node
    Node insert(Node root, int key) {
        // Return a new node if the tree is empty
        if (root == null) {
            return new Node(key);
        }

        // Traverse to the right place and insert the node
        if (key < root.key) {
            root.left = insert(root.left, key);
        } else {
            root.right = insert(root.right, key);
        }

        return root;
    }

    // Find the inorder successor
    Node minValueNode(Node root) {
        Node current = root;

        // Find the leftmost leaf
        while (current.left != null) {
            current = current.left;
        }

        return current;
    }

    // Deleting a node
    Node deleteNode(Node root, int key) {
        // Return if the tree is empty
        if (root == null) {
            return root;
        }

        // Find the node to be deleted
        if (key < root.key) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.key) {
            root.right = deleteNode(root.right, key);
        } else {
            // If the node is with only one child or no child
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // If the node has two children,
            // place the inorder successor in position of the node to be deleted
            root.key = minValueNode(root.right).key;

            // Delete the inorder successor
            root.right = deleteNode(root.right, root.key);
        }

        return root;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = tree.insert(tree.root, 9);
        tree.root = tree.insert(tree.root, 3);
        tree.root = tree.insert(tree.root, 2);
        tree.root = tree.insert(tree.root, 4);
        tree.root = tree.insert(tree.root, 7);
        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 15);
        tree.root = tree.insert(tree.root, 5);

        System.out.print("Inorder traversal: ");
        tree.inorder(tree.root);
        System.out.println();

        System.out.println("Delete 10");
        tree.root = tree.deleteNode(tree.root, 10);

        System.out.print("Inorder traversal: ");
        tree.inorder(tree.root);
    }
}
    

#include <iostream>

// Create a node
class Node {
public:
    int key;
    Node* left;
    Node* right;

    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

// Inorder traversal
void inorder(Node* root) {
    if (root != nullptr) {
        // Traverse left
        inorder(root->left);

        // Traverse root
        std::cout << root->key << "-> ";

        // Traverse right
        inorder(root->right);
    }
}

// Insert a node
Node* insert(Node* node, int key) {
    // Return a new node if the tree is empty
    if (node == nullptr)
        return new Node(key);

    // Traverse to the right place and insert the node
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);

    return node;
}

// Find the inorder successor
Node* minValueNode(Node* node) {
    Node* current = node;

    // Find the leftmost leaf
    while (current->left != nullptr)
        current = current->left;

    return current;
}

// Deleting a node
Node* deleteNode(Node* root, int key) {
    // Return if the tree is empty
    if (root == nullptr)
        return root;

    // Find the node to be deleted
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        // If the node is with only one child or no child
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }

        // If the node has two children,
        // place the inorder successor in position of the node to be deleted
        Node* temp = minValueNode(root->right);

        root->key = temp->key;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }

    return root;
}

int main() {
    Node* root = nullptr;
    root = insert(root, 9);
    root = insert(root, 3);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 7);
    root = insert(root, 10);
    root = insert(root, 15);
    root = insert(root, 5);

    std::cout << "Inorder traversal: ";
    inorder(root);
    std::cout << std::endl;

    std::cout << "Delete 10" << std::endl;
    root = deleteNode(root, 10);

    std::cout << "Inorder traversal: ";
    inorder(root);
    std::cout << std::endl;

    return 0;
}
    

Output

Inorder traversal:  2-> 3-> 4-> 5-> 7-> 9-> 10-> 15-> 
Delete 10
Inorder traversal:  2-> 3-> 4-> 5-> 7-> 9-> 15-> 

Complexity Analysis of Binary Search Tree Operations

1. Time Complexity

   Operations	Best Case	Average Case	Worst Case
   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)

2. Space Complexity

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

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.

Advantages of Binary Search Trees

1. Efficient searching: Due to the arrangement of the data 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: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.
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 Trees

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.

Summary

The tutorial covers all the aspects from definition to advantages and disadvantages of binary search trees in data structures. The binary search trees have multiple applications with multiple advantages. Therefore refer to the tutorial until you get thorough with every detail of the binary search tree. To test your knowledge of binary search trees, enroll in our Dsa Course Online.