Binary Search Tree (BST)

---

Introduction

Binary Search Trees (BSTs) are a fundamental data structure in computer science that combine the hierarchical structure of binary trees with the power of ordering to enable efficient searching, insertion, and deletion. If you're preparing for coding interviews or aiming to strengthen your data structures knowledge, mastering BSTs is essential.

In this blog, we will explore BST concepts in depth, discuss key properties, implement core operations in Java, analyze time complexity, and provide practice problems to level up your skills.

---

What is a Binary Search Tree?

A Binary Search Tree is a binary tree with the following property:

For every node, all nodes in the left subtree have values less than the node's value, and all nodes in the right subtree have values greater than the node's value.

This ordering property helps maintain a sorted structure, enabling efficient search and update operations.

Example BST

        15
       /  \
     10    20
     / \     \
    8  12     25

• All nodes in left subtree of 15 (8, 10, 12) are less than 15.

• All nodes in right subtree of 15 (20, 25) are greater than 15.

---

Key Properties of BST

• Ordering: Left subtree < Node < Right subtree for every node.

• No duplicates: Typically, BSTs do not allow duplicates. If needed, duplicates can be stored either consistently in the left or right subtree.

• Height and Balance: The height affects efficiency. Balanced BSTs maintain height ≈ O(log n). Unbalanced BSTs degrade to O(n) height.

• Recursive Structure: Each subtree is itself a BST.

---

Java Implementation of BST Node

public class TreeNode {
    int val;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}

---

Basic Operations on BST in Java

1. Search in BST

Search is efficient due to the ordering property — at each node, decide to go left or right.

public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || root.val == val)
        return root;

    if (val < root.val)
        return searchBST(root.left, val);
    else
        return searchBST(root.right, val);
}

---

2. Insertion in BST

Insert a new value by maintaining the BST property. Recursively find the correct position.

public TreeNode insertBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }

    if (val < root.val) {
        root.left = insertBST(root.left, val);
    } else if (val > root.val) {
        root.right = insertBST(root.right, val);
    }
    // If val == root.val, duplicates not allowed; ignore or handle separately
    return root;
}

---

3. Deletion in BST

Deleting a node is trickier and involves 3 cases:

• Leaf node: Remove node directly.

• One child: Replace node with child.

• Two children: Replace node’s value with the inorder successor (smallest in right subtree), then delete the successor node.

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

    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        // Node to be deleted found
        if (root.left == null) return root.right;
        else if (root.right == null) return root.left;

        // Node with two children: Get inorder successor (smallest in right subtree)
        root.val = minValue(root.right);

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

private int minValue(TreeNode node) {
    int minv = node.val;
    while (node.left != null) {
        minv = node.left.val;
        node = node.left;
    }
    return minv;
}

---

4. Inorder Traversal (Sorted order output)

Inorder traversal visits nodes in sorted order (left, root, right):

public void inorderTraversal(TreeNode root) {
    if (root != null) {
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }
}

---

Time Complexity Analysis of BST Operations

• The average case assumes a balanced tree.

• Worst case happens when the tree is skewed (like a linked list).

---

Real-world Analogy

Think about searching for a contact in a sorted phonebook rather than a random list. Because the entries are sorted, you can quickly narrow down the search by dividing the book in half repeatedly — just like BST’s divide-and-conquer approach.

---

Practice Problems

---

Tips for Interview Prep

• Understand the BST ordering property deeply.

• Implement recursive and iterative solutions for search, insert, and delete.

• Handle edge cases: empty tree, duplicates, single child nodes.

• Know how to find the inorder successor and predecessor.

• Practice tree traversals (inorder, preorder, postorder).

• Remember balancing affects performance; understand basics of AVL/Red-Black trees (optional).

---

Wrapping Up

BSTs are crucial data structures enabling fast lookup, insertion, and deletion. Their sorted nature allows algorithms to run in logarithmic time on balanced trees, making them extremely useful in many applications.

Mastering BST operations and understanding their time complexities will give you a significant edge in interviews and coding challenges.

---

🙌 Enjoying the Series?

This blog is part of my DSA series — “Level Up Your Programming with Nitin”, where I break down core data structures and algorithms with clear explanations, real-world analogies, Java code snippets, and curated LeetCode problems.

You can explore the entire series anytime here:
🔗 DS Interview Prep Series

If you find it helpful, feel free to share with peers, bookmark it for revision, or leave a ❤️ to support the effort.

🔗 Follow my blog on Hashnode: ns717.hashnode.dev
💼 Connect with me on LinkedIn: Nitin Singh

Thanks for reading, and happy coding! 💻🌳