Binary Search Tree

A Binary Search Tree (BST) is a node-based binary tree data structure which has the following propetries:

• The left subtree of a node contains only nodes with keys lesser than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes.

Below is a Java implementation demonstrating the core operations: insertion, deletion, and traversal.

public class BinarySearchTree {

    // Inner class representing a node in the tree
    static class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode parent;

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

    /**
     * Creates a Binary Search Tree from an array of integers.
     * @param values The array of integers to insert into the tree.
     * @return The root node of the created tree.
     */
    public TreeNode createBST(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        for (int i = 1; i < values.length; i++) {
            insert(root, values[i]);
        }
        return root;
    }

    /**
     * Recursively inserts a new value into the BST.
     * @param root The root of the subtree to insert into.
     * @param value The value to insert.
     * @return The (possibly new) root of the subtree.
     */
    public TreeNode insert(TreeNode root, int value) {
        if (root == null) {
            return new TreeNode(value);
        }

        if (value < root.data) {
            root.left = insert(root.left, value);
            if (root.left != null) {
                root.left.parent = root;
            }
        } else if (value > root.data) {
            root.right = insert(root.right, value);
            if (root.right != null) {
                root.right.parent = root;
            }
        }
        // If value == root.data, we do nothing (no duplicates allowed)
        return root;
    }

    /**
     * Deletes a node with the given value from the BST.
     * @param root The root of the tree.
     * @param value The value to delete.
     * @return The root of the modified tree.
     */
    public TreeNode delete(TreeNode root, int value) {
        if (root == null) {
            return null;
        }

        // 1. Find the node to delete
        if (value < root.data) {
            root.left = delete(root.left, value);
        } else if (value > root.data) {
            root.right = delete(root.right, value);
        } else {
            // 2. Node with only one child or no child
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // 3. Node with two children: Get the inorder successor (smallest in the right subtree)
            TreeNode successor = findMin(root.right);

            // Copy the inorder successor's data to this node
            root.data = successor.data;

            // Delete the inorder successor
            root.right = delete(root.right, successor.data);
        }
        return root;
    }

    /**
     * Finds the node with the minimum value in a given subtree.
     * @param node The root of the subtree.
     * @return The node with the minimum value.
     */
    public TreeNode findMin(TreeNode node) {
        TreeNode current = node;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }

    /**
     * Performs an in-order traversal of the tree, printing node values.
     * This will print the tree's values in ascending order.
     * @param node The root of the subtree to traverse.
     */
    public void inOrderTraversal(TreeNode node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.data + " ");
            inOrderTraversal(node.right);
        }
    }

    /**
     * Performs an iterative pre-order traversal of the tree.
     * @param root The root of the tree.
     */
    public void preOrderTraversalIterative(TreeNode root) {
        if (root == null) {
            return;
        }

        java.util.Stack<treenode> stack = new java.util.Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode currentNode = stack.pop();
            System.out.print(currentNode.data + " ");

            // Push right child first so that left child is processed first
            if (currentNode.right != null) {
                stack.push(currentNode.right);
            }
            if (currentNode.left != null) {
                stack.push(currentNode.left);
            }
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] values = {15, 10, 20, 8, 12, 17, 25, 6, 11, 16, 27};

        TreeNode root = bst.createBST(values);
        System.out.println("In-order traversal of the BST:");
        bst.inOrderTraversal(root);
        System.out.println("
");

        System.out.println("Deleting node with value 10...");
        root = bst.delete(root, 10);
        System.out.println("In-order traversal after deletion:");
        bst.inOrderTraversal(root);
        System.out.println("
");

        System.out.println("Iterative pre-order traversal:");
        bst.preOrderTraversalIterative(root);
    }
}
</treenode>