Implementing Binary Search Tree (BST) Operations in Java

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

Binary Search Trees (BST) are essential data structures that allow for efficient insertion, deletion, and search operations. In this blog post, we will walk through the implementation of a BST in Java, focusing on the primary operations: insertion, deletion, and search.

Understanding BST 

A BST is a binary tree where every node has the following properties: 

• The left subtree of a node contains only nodes with keys less than the node's key. 
• The right subtree of a node contains only nodes with keys greater than the node's key. 
• Both the left and right subtrees are also BSTs. 

Program Implementation

// Class to represent nodes
class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

public class BinarySearchTree {

    // Root of BST
    Node root;

    // Constructor
    BinarySearchTree() {
        root = null;
    }

    // Insert a new key in BST
    void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }

        // Traverse down the tree
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);

        return root;
    }

    // This method mainly calls deleteRec()
    void delete(int key) {
        root = deleteRec(root, key);
    }

    Node deleteRec(Node root, int key) {
        if (root == null) return root;

        // Traverse the tree
        if (key < root.key)
            root.left = deleteRec(root.left, key);
        else if (key > root.key)
            root.right = deleteRec(root.right, key);
        else {
            // Node with one child or no child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            // Node with two children
            root.key = minValue(root.right);

            root.right = deleteRec(root.right, root.key);
        }
        return root;
    }

    int minValue(Node root) {
        int minValue = root.key;
        while (root.left != null) {
            minValue = root.left.key;
            root = root.left;
        }
        return minValue;
    }

    // Search a key in BST
    boolean search(int key) {
        return searchRec(root, key);
    }

    boolean searchRec(Node root, int key) {
        if (root == null) return false;
        if (root.key == key) return true;

        if (key < root.key)
            return searchRec(root.left, key);
        return searchRec(root.right, key);
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        tree.insert(50);
        tree.insert(30);
        tree.insert(70);
        tree.insert(20);
        tree.insert(40);
        tree.insert(60);
        tree.insert(80);

        System.out.println(tree.search(25)); // Output: false
        System.out.println(tree.search(70)); // Output: true

        tree.delete(20);
        System.out.println(tree.search(20)); // Output: false
    }
}

Step-by-step Explanation

Node Class:

• Represents each node in our BST. Contains an integer key and pointers to left and right child nodes. 

insert() and insertRec(): 

• These methods help insert a new key into the BST. Using recursion, they traverse the tree to find the correct position and then insert the key. 

delete() and deleteRec(): 

• Used to delete a key from the BST. The deleteRec() function uses recursion to find the node to be deleted. If the node has one or no child, it deletes the node. For nodes with two children, it finds the inorder successor (smallest value in the right subtree) and replaces the node's key with this value.

search() and searchRec(): 

• These methods help check if a key exists in the BST. They use recursion to traverse the tree in search of the key. 

main Method: 

• Here, we create a sample BST by inserting multiple keys. Then, we search for a few keys and print the results. Lastly, we delete a key and check if it's successfully removed by searching again. 

The key takeaway is the efficient manner in which BSTs perform these operations, with average time complexities often being logarithmic. This efficiency, combined with the clear structure and recursive nature of BST operations, makes it a favorite data structure for many algorithms and applications.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Build REST APIs with Spring Boot 4, Spring Security 7, and JWT

🆕 High-Demand 80–90% OFF

[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25

🆕 High-Demand 80–90% OFF

ChatGPT + Generative AI + Prompt Engineering for Beginners

🚀 Trending Now 80–90% OFF

Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Real-Time REST APIs with Spring Boot - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Microservices with Spring Boot and Spring Cloud

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Java Full-Stack Developer Course with Spring Boot and React JS

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Build 5 Spring Boot Projects with Java: Line-by-Line Coding

🌟 Top Rated 80–90% OFF

Testing Spring Boot Application with JUnit and Mockito

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot Thymeleaf Real-Time Web Application - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Master Spring Data JPA with Hibernate

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot + Apache Kafka Course - The Practical Guide

🎓 Student Favorite 80–90% OFF
Available in Udemy for Business

Java Testing: Mastering JUnit 5 Framework

🆕 New 80–90% OFF

Reactive Programming in Java: Spring WebFlux and Testing

🌟 Top Rated 80–90% OFF

Spring Boot + RabbitMQ Course - The Practical Guide

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Functional Programming in Java (Includes Java Collections)

🎓 Student Favorite 80–90% OFF

ChatGPT for Java Developers: Boost Your Productivity with AI

🚀 Trending Now 80–90% OFF