Binary Search Tree from Scratch in Java

Introduction
A Binary Search Tree (BST) is a type of binary tree where each node has at most two children, referred to as the left child and the right child. For each node, the left subtree contains only nodes with values less than the node’s value, and the right subtree contains only nodes with values greater than the node’s value. BSTs are used for efficient searching, insertion, and deletion operations.

Why Use a Binary Search Tree?
BSTs offer several advantages:

Efficient Searching: Average time complexity is O(log n) for search, insertion, and deletion.
Dynamic Set of Items: Supports dynamic operations, unlike static arrays.
Ordered Elements: The in-order traversal of a BST yields elements in a sorted order.
Step-by-Step Guide to Building a BST
Step 1: Define the Node Structure
The first step is to define the structure of a node in the tree. Each node will have three attributes: a value, a reference to the left child, and a reference to the right child.

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

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

Step 2: Create the BST Class with Constructor
Next, we create the BST class that contains a reference to the root of the tree and the methods for inserting elements.

public class BinarySearchTree {
    TreeNode root;

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

Step 3: Implement the Insertion Method
To insert an element into the BST, we need to find the correct position for the new node. The insertion method is usually implemented as a recursive function.

public void insert(int value) {
    root = insertRec(root, value);
}

private TreeNode insertRec(TreeNode root, int value) {
    // Base case: if the tree is empty, return a new node
    if (root == null) {
        root = new TreeNode(value);
        return root;
    }

    // Otherwise, recur down the tree
    if (value < root.value) {
        root.left = insertRec(root.left, value);
    } else if (value > root.value) {
        root.right = insertRec(root.right, value);
    }

    // Return the (unchanged) node pointer
    return root;
}

Visualization
To better understand how the insertion works, let's consider an example. Suppose we want to insert the following sequence of numbers into the BST: 50, 30, 70, 20, 40, 60, 80.

50

  50
 /
30

  50
 /  \
30  70

50
 /  \
30  70
/

Insert 40:

  50
 /  \
30  70
/ \

Insert 60

  50
 /  \
30  70
/ \  /

Insert 80:

  50
 /  \
30  70
/ \  / \

Complete Code
Here's the complete code for creating a BST and inserting elements:

public class BinarySearchTree {
    TreeNode root;

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

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value < root.value) {
            root.left = insertRec(root.left, value);
        } else if (value > root.value) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    // Additional methods for traversal, search, and delete can be added here

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int value : values) {
            bst.insert(value);
        }

        // Add code to print or traverse the tree
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

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