Binary Search Trees

Binary Search Trees (BSTs)

A Binary Search Tree (BST) is a type of binary tree where each node follows these rules:

1. The value of every node in the left subtree is less than the value of the parent.
2. The value of every node in the right subtree is greater than the value of the parent.
3. Both the left and right subtrees are themselves BSTs.

This property makes BSTs highly efficient for searching, insertion, and deletion operations, which are typically faster than operations on other data structures like arrays or linked lists.

---

Structure of a Binary Search Tree

A node in a BST has the following:

1. Value: The data stored in the node.
2. Left Pointer: Points to the left child (smaller values).
3. Right Pointer: Points to the right child (larger values).

Example of a BST:

        50
      /    \
    30      70
   /  \    /  \
  20   40 60   80

• Left subtree contains nodes smaller than 50.
• Right subtree contains nodes larger than 50.

---

Operations on Binary Search Tree

1. Search

To find a value in a BST:

• Start from the root.
• Compare the value with the root:
  • If it matches, the search is successful.
  • If it’s smaller, move to the left subtree.
  • If it’s larger, move to the right subtree.
• Repeat this process until the value is found or the subtree becomes empty.

C++ Implementation:

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};

bool search(TreeNode* root, int key) {
    if (root == nullptr) return false; // Key not found
    if (root->data == key) return true; // Key found
    if (key < root->data) 
        return search(root->left, key); // Search in left subtree
    else 
        return search(root->right, key); // Search in right subtree
}

2. Insertion

To insert a new value in a BST:

1. Start at the root.
2. Compare the new value with the current node:
   • If it’s smaller, go to the left subtree.
   • If it’s larger, go to the right subtree.
3. Insert the new value at the first empty position.

C++ Implementation:

TreeNode* insert(TreeNode* root, int value) {
    if (root == nullptr) return new TreeNode(value); // Create a new node
    if (value < root->data) 
        root->left = insert(root->left, value); // Insert in left subtree
    else if (value > root->data) 
        root->right = insert(root->right, value); // Insert in right subtree
    return root;
}

3. Deletion

Deleting a node in a BST has three cases:

1. Leaf Node (no children):
   • Simply remove the node.
2. One Child:
   • Replace the node with its child.
3. Two Children:
   • Replace the node with the inorder successor (smallest node in the right subtree).

C++ Implementation:

TreeNode* findMin(TreeNode* root) {
    while (root->left != nullptr) root = root->left;
    return root; // Smallest node in the right subtree
}

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr) return root;
    if (key < root->data)
        root->left = deleteNode(root->left, key); // Search in left subtree
    else if (key > root->data)
        root->right = deleteNode(root->right, key); // Search in right subtree
    else {
        // Node with only one child or no child
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        // Node with two children
        TreeNode* temp = findMin(root->right); // Inorder successor
        root->data = temp->data; // Replace with successor's value
        root->right = deleteNode(root->right, temp->data); // Delete successor
    }
    return root;
}

4. Traversal

BSTs can be traversed using Inorder, Preorder, or Postorder traversals.

• Inorder Traversal (Left → Root → Right): Outputs values in ascending order for a BST.
• Preorder Traversal (Root → Left → Right): Useful for creating a copy of the tree.
• Postorder Traversal (Left → Right → Root): Used for deleting the tree.

---

Advantages of BST

1. Efficient Searching:
   • Average time complexity: $O(\log n)$
   • Worst-case (unbalanced tree): $O(n)$
2. Efficient Insertion and Deletion:
   • Similar complexity to searching.
3. Sorted Data:
   • Inorder traversal gives sorted order of elements.

---

Disadvantages of BST

1. Unbalanced Tree:
   • If the tree becomes unbalanced (e.g., all elements inserted in increasing order), it degenerates into a linked list, making operations $O(n)$.
   • To address this, we use balanced BSTs like AVL Trees or Red-Black Trees.

---

Applications of BST

1. Databases: Searching and storing data efficiently.
2. File Systems: Organizing and retrieving files.
3. Network Routing: Searching for routes quickly.
4. Implementing Maps and Sets: Many programming languages use BSTs internally for data structures like maps and sets.

---

Example: BST in Action

Given Data: Insert values 50, 30, 70, 20, 40, 60, 80.

Steps:

1. Insert 50 → Root node.
2. Insert 30 → Goes to left of 50.
3. Insert 70 → Goes to right of 50.
4. Insert 20 → Goes to left of 30.
5. Insert 40 → Goes to right of 30.
6. Insert 60 → Goes to left of 70.
7. Insert 80 → Goes to right of 70.

Resulting Tree:

        50
      /    \
    30      70
   /  \    /  \
  20   40 60   80

Inorder Traversal Output: 20 30 40 50 60 70 80
Preorder Traversal Output: 50 30 20 40 70 60 80
Postorder Traversal Output: 20 40 30 60 80 70 50

---