Home › DSA › Trees

BST Operations

Binary Search Trees (BSTs) provide efficient operations for searching, inserting, and deleting elements while maintaining their sorted structure. Each of these operations leverages the BST property—where the left subtree contains values smaller than the node, and the right subtree contains values greater than the node.

In this lesson, we will cover the three primary operations on BSTs:

Insertion - Adding a new node while maintaining the BST structure.
Searching - Finding a node in the BST efficiently.
Deletion - Removing a node while preserving BST properties.

Each operation follows a recursive approach, breaking down the problem into smaller subproblems, making traversal more structured. Let's explore each operation in detail.

1. BST Insertion

Insertion in a Binary Search Tree (BST) requires finding the correct position while maintaining the BST property. Starting from the root, we compare the new value with the current node. If the value is smaller, we move to the left subtree; if greater, we move to the right. Once an empty spot is found, the new node is inserted.

Step-by-Step Algorithm

If the BST is empty, create a new node and set it as the root.
Start at the root and compare the new value with the current node’s value:
- If the value is smaller, move to the left subtree.
- If the value is greater, move to the right subtree.
Repeat recursively until we find an empty spot (NULL).
Insert the new node at the found position, maintaining the BST structure.

java

// Class to define a node in the BST
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     // Constructor to initialize a node
//     TreeNode(int val) {
//         this.val = val;
//         this.left = null;
//         this.right = null;
//     }
// }

class Solution {
    TreeNode root; // Root of the BST

    // Recursive method for inserting a value in the BST
    TreeNode insert(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val); // Insert new node at the correct position
        }

        if (val < node.val) {
            node.left = insert(node.left, val); // Recur for left subtree
        } else if (val > node.val) {
            node.right = insert(node.right, val); // Recur for right subtree
        } else {
            System.out.println("Duplicate value " + val + " not allowed in BST.");
        }

        return node; // Return unchanged node
    }

    // Method to print BST in inorder traversal (Left -> Root -> Right)
    void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.val + " "); // Print node value
        inorder(node.right);
    }

    public static void main(String[] args) {
        Solution bst = new Solution();

        bst.root = bst.insert(bst.root, 8);
        bst.insert(bst.root, 5);
        bst.insert(bst.root, 3);
        bst.insert(bst.root, 7);
        bst.insert(bst.root, 2);
        bst.insert(bst.root, 4);
        bst.insert(bst.root, 6);
        bst.insert(bst.root, 8); // Attempting to insert duplicate 8

        System.out.println("BST Insertion Completed.");
        System.out.print("Inorder Traversal (Sorted Order): ");
        bst.inorder(bst.root);
    }
}

Time Complexity

Best and Average Case:
- Each step eliminates half the remaining elements, making it logarithmic.
Worst Case (Skewed Tree):
- If the tree is completely unbalanced (like a linked list), insertion takes linear time.

Space Complexity

, where h is the height of the tree
Recursive calls take stack space proportional to the tree height.

2. BST Searching

Searching in a BST efficiently finds a given value by leveraging the BST property. Like insertion, we start from the root and decide whether to move left or right based on comparisons.

Step-by-Step Algorithm

If the BST is empty, return "Not Found."
Start at the root and compare the search key with the current node’s value:
- If the key matches, return the node.
- If the key is smaller, move to the left subtree.
- If the key is greater, move to the right subtree.
Repeat recursively until the value is found or the search ends at a NULL pointer.

Code

java

// Class to define a node in the BST
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     // Constructor to initialize a node
//     TreeNode(int val) {
//         this.val = val;
//         this.left = null;
//         this.right = null;
//     }
// }

class Solution {
    // Recursive method for searching a value in the BST
    TreeNode search(TreeNode node, int key) {
        if (node == null || node.val == key) {
            return node; // Node found or tree is empty
        }

        if (key < node.val) {
            return search(node.left, key); // Recur for left subtree
        }

        return search(node.right, key); // Recur for right subtree
    }

    public static void main(String[] args) {
        Solution bst = new Solution();

        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(8);

        int key = 6; // Searching for key 6
        TreeNode result = bst.search(root, key);
        if (result != null) {
            System.out.println("Key " + key + " found in BST.");
        } else {
            System.out.println("Key " + key + " not found in BST.");
        }
    }
}

Time Complexity

In a balanced BST, searching takes because we eliminate half of the remaining elements at each step, similar to binary search.
In the worst case (skewed tree), searching takes as we may have to traverse all nodes in a single branch.
The best case is if the root contains the key.

Space Complexity

Space Complexity is for recursive in balanced, in skewed BST).

3. BST Deletion

Deleting a node from a Binary Search Tree (BST) requires adjusting the tree structure while ensuring that the BST property remains intact. The complexity of deletion varies depending on the number of children the node has.

We need to handle three cases:

Leaf Node (No Children): If the node is a leaf, it is simply removed from the tree.
Node with One Child: If the node has only one child, we replace it with its child, bypassing the node.
Node with Two Children: We replace the node's value with the inorder successor (smallest value in the right subtree) and then recursively delete the successor node.

By following these steps, we ensure the BST remains valid while removing the specified node.

Step-by-Step Algorithm

Handle the Base Case:
- If the tree is empty (node == null), return null as there is nothing to delete.
Traverse the Tree to Find the Node to Delete:
- If the key to delete is smaller than the current node’s value (key < node.val), recursively search in the left subtree by calling delete(node.left, key).
- If the key is greater than the current node’s value (key > node.val), recursively search in the right subtree by calling delete(node.right, key).
Node to be Deleted is Found:
- If key == node.val, proceed to handle the deletion cases.
Case 1: Node Has No Left Child (Only Right Child or Leaf Node)
- If node.left == null, return node.right, effectively removing the current node.
Case 2: Node Has No Right Child (Only Left Child)
- If node.right == null, return node.left, effectively removing the current node.
Case 3: Node Has Two Children (Both Left and Right Exist)
- Find the inorder successor, which is the smallest node in the right subtree.
- Use the helper function minValueNode(node.right) to locate this successor.
- Copy the inorder successor's value to the current node (node.val = successor.val).
- Recursively delete the successor node from the right subtree using delete(node.right, successor.val).
Return the Updated Node:
- After handling all cases, return the updated node to maintain the tree structure.

This algorithm ensures that the BST properties are preserved after deletion.

Code

java

// Class to define a node in the BST
// class TreeNode {
//     int val;            // Value stored in the node
//     TreeNode left;      // Pointer to the left child
//     TreeNode right;     // Pointer to the right child

//     // Constructor to initialize a node
//     TreeNode(int val) {
//         this.val = val;
//         this.left = null;
//         this.right = null;
//     }
// }

class Solution {
    TreeNode root; // Root of the BST

    // Recursive method for deleting a node in the BST
    TreeNode delete(TreeNode node, int key) {
        if (node == null) return null; // Base case: If node is not found

        // Traverse left or right subtree based on the key
        if (key < node.val) {
            node.left = delete(node.left, key);
        } else if (key > node.val) {
            node.right = delete(node.right, key);
        } else { // Node found, handle deletion
            // Case 1: Node has no left child
            if (node.left == null) return node.right;
            // Case 2: Node has no right child
            if (node.right == null) return node.left;

            // Case 3: Node has two children
            TreeNode successor = minValueNode(node.right); // Find inorder successor
            node.val = successor.val; // Copy the successor's value
            node.right = delete(node.right, successor.val); // Delete the successor
        }
        return node;
    }

    // Helper method to find the inorder successor (smallest node in right subtree)
    TreeNode minValueNode(TreeNode node) {
        TreeNode current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }

    // Method to print BST in inorder traversal (Left -> Root -> Right)
    void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.val + " "); // Print node value
        inorder(node.right);
    }

    public static void main(String[] args) {
        Solution bst = new Solution();

        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(8);

        System.out.println("Original BST (Inorder Traversal):");
        bst.inorder(root);
        System.out.println();

        // Delete nodes from BST
        int keyToDelete = 3;
        System.out.println("\nDeleting node " + keyToDelete + "...");
        root = bst.delete(root, keyToDelete);

        System.out.println("BST after deletion (Inorder Traversal):");
        bst.inorder(root);
    }
}

Time Complexity

in a balanced BST because we eliminate half of the nodes at each step while traversing.
in a skewed BST as we may need to traverse all nodes if the tree is unbalanced.

Space Complexity

for recursive approach due to recursive calls up to the tree height (log n in balanced BST).

Issues with BSTs

Binary Search Trees (BSTs) have several issues and limitations that can affect their performance and efficiency in specific scenarios. Some of the key issues with BSTs include:

Unbalanced BSTs: BSTs can become unbalanced due to the order in which elements are inserted. The tree can degenerate into a linked list if elements are inserted in a sorted or nearly sorted order. Unbalanced BSTs lead to poor time complexities for searching, insertion, and deletion operations, becoming closer to linear time instead of the optimal logarithmic time .

Example: A BST with elements inserted in sorted order: 1, 2, 3, 4.

Degenerate Trees: Degenerate trees are extreme cases of unbalanced BSTs where each node has only one child, essentially forming a linked list. Degenerate trees result in very poor time complexities for all operations, rendering the advantages of using BSTs ineffective.

Example: A degenerate BST with elements inserted in descending order: 4, 3, 2, 1.

Performance Issues: Unbalanced and degenerate BSTs can lead to significantly degraded performance for common operations like searching, insertion, and deletion. In the worst-case scenario, when the tree is degenerate, these operations can take linear time , negating the primary benefit of using a BST.
Complex Balancing: Ensuring a BST remains balanced after insertion and deletion requires complex balancing algorithms. While self-balancing BSTs like AVL trees and Red-Black trees exist, implementing and maintaining these balancing mechanisms adds overhead and complexity to the code.
Lack of Unique Keys: BSTs generally do not support duplicate keys. The behavior might vary depending on the implementation when attempting to insert a duplicate key. Some implementations might overwrite the existing value, while others might reject the insertion.
Memory Overhead: Each node in a BST requires additional memory for storing pointers to the left and right children. The memory overhead can become significant for large datasets, especially if the tree is poorly balanced.
Not Suitable for Dynamic Datasets: BSTs are not well-suited for datasets that frequently change in size. Insertions and deletions can lead to imbalanced trees, requiring additional balancing operations, which can be computationally expensive.
Limited Search Performance for Equal Keys: While BSTs provide efficient search times for unique keys, searching for the next greater or lesser element for equal keys requires additional operations and may be less efficient.

🤖 Don't fully get this? Learn it with Claude

Stuck on BST Operations? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **BST Operations** (DSA) and want to truly understand it. Explain BST Operations from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **BST Operations** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **BST Operations** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **BST Operations** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← BST Traversal Techniques Introduction to Level Order Traver →