Binary Search Tree in Java (Complete Guide with Insertion, Deletion and Searching)

 Binary Search Tree (Deep Concept Guide)

Level: Beginner to Advanced

---

 What is a Binary Search Tree?

A Binary Search Tree (BST) is a special type of binary tree that follows a specific ordering property: for every node, all elements in the left subtree are smaller than the node’s value, and all elements in the right subtree are greater than the node’s value. This property is recursively applied to every node in the tree. Because of this ordering, BST allows efficient searching, insertion, and deletion operations. BST is widely used in applications like databases, search engines, and indexing systems where fast lookup is required. The performance of BST depends on its structure; a balanced BST provides optimal efficiency.

---

 BST Property (Most Important Rule)

For every node:

 Left subtree < Root < Right subtree

Example:

        10
       /  \
      5    15
     / \     \
    2   7     20

---

 Why BST Powerful?

• Searching fast ho jata hai

• Sorted data milta hai (Inorder traversal se)

• Efficient insert/delete

---

 Real Life Example (Student Friendly)

 Example – Dictionary

Dictionary me words sorted hote hain.

Agar tum “Mango” search karte ho:

• Pehle middle word check karte ho

• Fir left ya right side jaate ho

Ye BST jaisa hi kaam karta hai.

---

 Operations in BST

---

 Insertion

Concept

• Root se start karo

• Compare karo

• Left ya right move karo

• Null milte hi insert karo

---

Java Code (Insertion)

TreeNode insert(TreeNode root, int key) {
    if (root == null)
        return new TreeNode(key);

    if (key < root.data)
        root.left = insert(root.left, key);
    else
        root.right = insert(root.right, key);

    return root;
}

---

 Searching

Concept

• Key compare karo

• Left ya right move karo

• Match milte hi return

---

Java Code (Search)

boolean search(TreeNode root, int key) {
    if (root == null)
        return false;

    if (root.data == key)
        return true;

    if (key < root.data)
        return search(root.left, key);
    else
        return search(root.right, key);
}

---

 Deletion (Important)

3 cases:

• Leaf node

• One child

• Two children

---

Java Code (Delete)

TreeNode delete(TreeNode root, int key) {
    if (root == null) return root;

    if (key < root.data)
        root.left = delete(root.left, key);
    else if (key > root.data)
        root.right = delete(root.right, key);
    else {
        if (root.left == null)
            return root.right;
        else if (root.right == null)
            return root.left;

        root.data = minValue(root.right);
        root.right = delete(root.right, root.data);
    }
    return root;
}

int minValue(TreeNode root) {
    while (root.left != null)
        root = root.left;
    return root.data;
}

---

 Time Complexity (Deep Understanding)

• Best Case → O(log n)

• Average Case → O(log n)

• Worst Case → O(n) (skewed tree)

---

 Advantages

• Fast searching

• Sorted data access

• Efficient insert/delete

---

 Disadvantages

• Skewed tree ban sakta hai

• Balancing required (AVL, Red-Black Tree)

---

 BST vs Binary Tree

Feature	Binary Tree	BST
Ordering	No rule	Left < Root < Right
Search	O(n)	O(log n)

---

 Basic Question

BST me inorder traversal ka output kaisa hota hai?

---

Thinking Question

Agar BST sorted input se banaya jaye to kya problem hogi?