AntInLoop

Binary Search Tree (BST) Code Implementations

Production-ready Binary Search Tree (BST) data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.

Study Binary Search Tree (BST) Guide ยท Launch Visualizer

CPP Implementation

// Binary Search Tree Implementation in Java
class BinarySearchTree {

    // Node structure
    static class Node {
        int data;
        Node left, right;

        Node(int val) {
            data = val;
            left = right = null;
        }
    }

    Node root;

    BinarySearchTree() {
        root = null;
    }

    // Insert a node
    Node insert(Node node, int val) {
        if (node == null) {
            return new Node(val);
        }
        if (val < node.data) {
            node.left = insert(node.left, val);
        } else if (val > node.data) {
            node.right = insert(node.right, val);
        }
        return node;
    }

    void insert(int val) {
        root = insert(root, val);
    }

    // Search for a value
    boolean search(Node node, int val) {
        if (node == null) return false;
        if (node.data == val) return true;
        if (val < node.data)
            return search(node.left, val);
        else
            return search(node.right, val);
    }

    boolean search(int val) {
        return search(root, val);
    }

    // Delete a node
    Node delete(Node node, int val) {
        if (node == null) return null;

        if (val < node.data) {
            node.left = delete(node.left, val);
        } else if (val > node.data) {
            node.right = delete(node.right, val);
        } else {
            // Case 1: Node with only one child or no child
            if (node.left == null) return node.right;
            else if (node.right == null) return node.left;

            // Case 2: Node with two children -> inorder successor
            node.data = minValue(node.right);
            node.right = delete(node.right, node.data);
        }
        return node;
    }

    void delete(int val) {
        root = delete(root, val);
    }

    int minValue(Node node) {
        int min = node.data;
        while (node.left != null) {
            min = node.left.data;
            node = node.left;
        }
        return min;
    }

    // Inorder Traversal (Left, Root, Right)
    void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.data + " ");
        inorder(node.right);
    }

    void inorder() {
        inorder(root);
        System.out.println();
    }

    // Preorder Traversal (Root, Left, Right)
    void preorder(Node node) {
        if (node == null) return;
        System.out.print(node.data + " ");
        preorder(node.left);
        preorder(node.right);
    }

    void preorder() {
        preorder(root);
        System.out.println();
    }

    // Postorder Traversal (Left, Right, Root)
    void postorder(Node node) {
        if (node == null) return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.data + " ");
    }

    void postorder() {
        postorder(root);
        System.out.println();
    }

    // Main method
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // Insert nodes
        bst.insert(50);
        bst.insert(30);
        bst.insert(70);
        bst.insert(20);
        bst.insert(40);
        bst.insert(60);
        bst.insert(80);

        System.out.print("Inorder Traversal: ");
        bst.inorder();

        System.out.print("Preorder Traversal: ");
        bst.preorder();

        System.out.print("Postorder Traversal: ");
        bst.postorder();

        System.out.println("Search 40: " + (bst.search(40) ? "Found" : "Not Found"));
        System.out.println("Search 25: " + (bst.search(25) ? "Found" : "Not Found"));

        System.out.println("Deleting 20...");
        bst.delete(20);
        bst.inorder();

        System.out.println("Deleting 30...");
        bst.delete(30);
        bst.inorder();

        System.out.println("Deleting 50...");
        bst.delete(50);
        bst.inorder();
    }
}