Binary Search Tree Implementation

About

A Binary Search Tree (BST) is a binary tree where:

• Left child contains values less than the parent node.

• Right child contains values greater than the parent node.

• No duplicate values are allowed.

1. TreeNode Class – Represents a node with data, left, and right references.

2. BinarySearchTree Class – Implements common BST operations:

   • Insert

   • Search

   • Traversals (Inorder, Preorder, Postorder)

   • Deletion

   • Level-order traversal (BFS)

Java Implementation

// Node class representing each element in the BST
class TreeNode {
    int data;
    TreeNode left, right;

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

// BST class implementing insert, search, delete, and traversals
class BinarySearchTree {
    private TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    // Insert a new value into the BST
    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            return new TreeNode(value);
        }
        if (value < root.data) {
            root.left = insertRec(root.left, value);
        } else if (value > root.data) {
            root.right = insertRec(root.right, value);
        }
        return root;
    }

    // Search for a value in the BST
    public boolean search(int value) {
        return searchRec(root, value);
    }

    private boolean searchRec(TreeNode root, int value) {
        if (root == null) return false;
        if (root.data == value) return true;
        return value < root.data ? searchRec(root.left, value) : searchRec(root.right, value);
    }

    // Delete a node from the BST
    public void delete(int value) {
        root = deleteRec(root, value);
    }

    private TreeNode deleteRec(TreeNode root, int value) {
        if (root == null) return null;

        if (value < root.data) {
            root.left = deleteRec(root.left, value);
        } else if (value > root.data) {
            root.right = deleteRec(root.right, value);
        } else {
            // Case 1: Node with one child or no child
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;

            // Case 2: Node with two children – find inorder successor (smallest in right subtree)
            root.data = minValue(root.right);
            root.right = deleteRec(root.right, root.data);
        }
        return root;
    }

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

    // Inorder traversal (Left, Root, Right) – Sorted order
    public void inorder() {
        inorderRec(root);
        System.out.println();
    }

    private void inorderRec(TreeNode root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }

    // Preorder traversal (Root, Left, Right)
    public void preorder() {
        preorderRec(root);
        System.out.println();
    }

    private void preorderRec(TreeNode root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preorderRec(root.left);
            preorderRec(root.right);
        }
    }

    // Postorder traversal (Left, Right, Root)
    public void postorder() {
        postorderRec(root);
        System.out.println();
    }

    private void postorderRec(TreeNode root) {
        if (root != null) {
            postorderRec(root.left);
            postorderRec(root.right);
            System.out.print(root.data + " ");
        }
    }

    // Level-order traversal (BFS using queue)
    public void levelOrder() {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode tempNode = queue.poll();
            System.out.print(tempNode.data + " ");
            if (tempNode.left != null) queue.add(tempNode.left);
            if (tempNode.right != null) queue.add(tempNode.right);
        }
        System.out.println();
    }
}

// Main class to test BST implementation
public class BSTDemo {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // Insert elements into BST
        bst.insert(50);
        bst.insert(30);
        bst.insert(70);
        bst.insert(20);
        bst.insert(40);
        bst.insert(60);
        bst.insert(80);

        System.out.println("Inorder traversal (Sorted order):");
        bst.inorder(); // 20 30 40 50 60 70 80

        System.out.println("Preorder traversal:");
        bst.preorder(); // 50 30 20 40 70 60 80

        System.out.println("Postorder traversal:");
        bst.postorder(); // 20 40 30 60 80 70 50

        System.out.println("Level order traversal:");
        bst.levelOrder(); // 50 30 70 20 40 60 80

        // Search for a value
        System.out.println("Search 40: " + bst.search(40)); // true
        System.out.println("Search 100: " + bst.search(100)); // false

        // Delete a node
        bst.delete(50);
        System.out.println("Inorder after deleting 50:");
        bst.inorder(); // 20 30 40 60 70 80
    }
}

Explanation of Methods

Method	Description
insert(value)	Inserts a new value in the BST.
search(value)	Searches for a value in the BST. Returns true if found.
delete(value)	Deletes a value from the BST, handling different cases.
inorder()	Prints nodes in sorted order (Left → Root → Right).
preorder()	Prints nodes in root-first order (Root → Left → Right).
postorder()	Prints nodes in root-last order (Left → Right → Root).
levelOrder()	Prints nodes level-wise (Breadth-First Search).

Time Complexity

Operation	Best Case (Balanced Tree)	Worst Case (Skewed Tree)
Insert	O(log N)	O(N)
Search	O(log N)	O(N)
Delete	O(log N)	O(N)
Traversal	O(N)	O(N)