1. Objective

The goal is to insert a new value into a Binary Search Tree while maintaining the BST property, which states:

• For any given node X:
  • All values in the left subtree are less than X.
  • All values in the right subtree are greater than X.

2. Rules for Insertion

To insert a value into a BST:

1. Start at the root.
2. Compare the value to be inserted with the current node.
3. If value < current node → go to left.
4. If value > current node → go to right.
5. Repeat steps 2–4 until you find a null child — insert the new node here.

3. Visual Example

Insert the value 45 into the following BST:

        50
       /  \
     30    70
    /  \   / \
  20   40 60 80

Step-by-step:

• 45 < 50 → Go left.
• 45 > 30 → Go right.
• 45 > 40 → Go right of 40 (which is null).
• Insert 45 as the right child of 40.

Updated Tree:

        50
       /  \
     30    70
    /  \   / \
  20   40 60 80
           \
           45

4. Java Implementation

Step 1: Tree Node Class

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

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

Step 2: Insertion Logic (Recursive)

class BinarySearchTree {
    TreeNode root;

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

    // Public insert method
    public void insert(int value) {
        root = insertRecursive(root, value);
    }

    // Recursive helper method
    private TreeNode insertRecursive(TreeNode current, int value) {
        if (current == null) {
            return new TreeNode(value);  // Place to insert
        }

        if (value < current.data) {
            current.left = insertRecursive(current.left, value);
        } else if (value > current.data) {
            current.right = insertRecursive(current.right, value);
        }

        // If value == current.data, do not insert (optional: allow duplicates to left/right)
        return current;
    }
}

Step 3: Testing the Insert

public class InsertIntoBSTDemo {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int val : values) {
            bst.insert(val);
        }

        // Insert a new value
        bst.insert(45);

        // Inorder should show values in sorted order
        System.out.print("Inorder Traversal: ");
        inorderPrint(bst.root);  // Expected: 20 30 40 45 50 60 70 80
    }

    // Simple Inorder Traversal
    public static void inorderPrint(TreeNode node) {
        if (node != null) {
            inorderPrint(node.left);
            System.out.print(node.data + " ");
            inorderPrint(node.right);
        }
    }
}

5. Iterative Version of Insertion (Alternative)

If you prefer not to use recursion, here’s an iterative version of insert:

public void insertIterative(int value) {
    TreeNode newNode = new TreeNode(value);

    if (root == null) {
        root = newNode;
        return;
    }

    TreeNode current = root;
    TreeNode parent = null;

    while (current != null) {
        parent = current;

        if (value < current.data) {
            current = current.left;
        } else if (value > current.data) {
            current = current.right;
        } else {
            return; // Duplicate, do not insert
        }
    }

    if (value < parent.data) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
}