Binary Search Tree (BST): Insertion, Traversal, Search & Deletion – Complete Guide

Table of Contents

1. Introduction to Binary Search Tree
2. What is a BST?
3. Key Properties of BST
4. BST Node Structure
5. BST Operations Overview
6. Insertion in BST
7. Traversal Algorithms
   • PreOrder
   • InOrder
   • PostOrder
8. Searching in BST
9. Deletion in BST
10. Real-World Example
11. Time Complexity Analysis
12. Advantages & Disadvantages
13. Conclusion
14. FAQs

1. Introduction to Binary Search Tree

A Binary Search Tree (BST) is a fundamental data structure in computer science that allows efficient searching, insertion, and deletion of data. It is widely used in applications like databases, file systems, and search engines.

2. What is a BST?

A Binary Search Tree is a special type of binary tree where:

• Left subtree contains values less than the root
• Right subtree contains values greater than the root
• Each subtree is also a BST

3. Key Properties of BST

• Each node has at most two children
• No duplicate elements (standard BST)
• InOrder traversal produces sorted output
• Efficient operations compared to linear structures

4. BST Node Structure

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

Node(int value) {
    data = value;
    left = right = NULL;
}
};

5. BST Operations Overview

The main operations performed on BST:

✔ Insertion

✔ Traversal

✔ Searching

✔ Deletion

6. Insertion in BST

Insertion maintains BST properties.

Node* insert(Node* root, int value) {
    if (root == NULL)
        return new Node(value);

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;
}

7. Traversal Algorithms

Traversal means visiting all nodes in a specific order.

PreOrder Traversal (Root → Left → Right)

void preorder(Node* root) {
    if (root == NULL) return;

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

InOrder Traversal (Left → Root → Right)

void inorder(Node* root) {
    if (root == NULL) return;

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

PostOrder Traversal (Left → Right → Root)

void postorder(Node* root) {
    if (root == NULL) return;

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

8. Searching in BST

Searching is efficient due to ordered structure.

bool search(Node* root, int key) {
    if (root == NULL)
        return false;

    if (root->data == key)
        return true;

    if (key < root->data)
        return search(root->left, key);

    return search(root->right, key);
}

9. Deletion in BST

Deletion is the most important and slightly complex operation.

🔹 Cases of Deletion:

1. Node is a Leaf → Simply remove
2. Node has One Child → Replace with child
3. Node has Two Children → Replace with InOrder Successor

Node* findMin(Node* root) {
    while (root->left != NULL)
        root = root->left;
    return root;
}

Node* deleteNode(Node* root, int key) {
    if (root == NULL)
        return NULL;

    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        // Case 1 & 2: Node with 0 or 1 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;
        }

        // Case 3: Node with 2 children
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

    return root;
}

10. Real-World Example

📚 Student Record Management System

• Students stored using roll numbers in BST
• Fast searching of student records
• Easy insertion and deletion of students

Example:

• Insert: 50, 30, 70, 20, 40
• Search student with roll no 40 → Efficient lookup
• Delete student → BST reorganizes itself

11. Time Complexity Analysis

12. Advantages & Disadvantages

✅ Advantages:

• Efficient searching and updates
• Maintains sorted order
• Flexible and dynamic

❌ Disadvantages:

• Can become unbalanced
• Worst-case performance degrades
• Requires extra memory

13. Conclusion

The Binary Search Tree (BST) is a powerful non-linear data structure that provides efficient operations for managing hierarchical and sorted data.

Mastering:

• Insertion
• Traversal
• Searching
• Deletion

is essential for advanced topics like:

• AVL Trees
• Red-Black Trees
• Heaps

14. FAQs

Q1: What is InOrder Successor?

The smallest value in the right subtree.

Q2: Why is BST efficient?

Because it reduces the search space at each step.

Q3: What is the main drawback?

Unbalanced trees degrade performance.