Welcome back to my blog, dear readers! Today, I'm stepping into the realm of Java and diving into Binary Search Trees (BSTs). Whether you're a seasoned Java developer or someone just getting started, I hope you'll find this exploration both informative and straightforward.

Let's jump right in!

Setting the Foundation: Node Class

To begin building a BST, we need to establish its foundation: the Node class. This class will serve as the blueprint for the elements we'll store in our tree. Each Node possesses an integer value, and potential links to two child nodes (left and right).

With our Node class in place, let's move on to the main act: the BinarySearchTree class.

The BinarySearchTree starts with a singular root node, which can be null if our tree is empty.

// This is the main BinarySearchTree class
package datastructures.Recursion;

public class BinarySearchTree {

    // Root of the BST
    Node root;

    // Internal Node class representing individual elements in the BST
    class Node {
        int value;       // Numeric value of the node
        Node left;       // Reference to the left child node
        Node right;      // Reference to the right child node

        // Constructor to initialize the node with a value
        Node(int value) {
            this.value = value;
        }
    }
}

Inserting a Value: The Non-Recursive Way

The insert method allows us to add values to our BST. If our tree is empty (i.e., the root is null), we'll simply place the new node at the root. If not, we'll traverse the tree until we find a suitable spot for our new value.

// Insert function to add values to the BST using a non-recursive approach
public boolean insert(int value) {
    // Create a new node with the given value
    Node newNode = new Node(value);
    // If the tree is empty, make the new node the root
    if (root == null) {
        root = newNode;
        return true;
    }
    // Start traversal from the root
    Node temp = root;
    while (true) {
        // Check for duplicate values; duplicates are not allowed in this BST
        if (newNode.value == temp.value) {
            return false;
        }
        // If the new value is less than the current node's value, go left
        if (newNode.value < temp.value) {
            if (temp.left == null) {
                temp.left = newNode;
                return true;
            }
            temp = temp.left;
        } 
        // Otherwise, go right
        else {
            if (temp.right == null) {
                temp.right = newNode;
                return true;
            }
            temp = temp.right;
        }
    }
}

Seek and You Shall Find: The Contains Method

Checking whether a value exists within our BST is done via the contains method. Starting at the root, we traverse through the BST, moving left or right based on our target value.

// Function to check if a value exists within the BST (non-recursive approach)
public boolean contains(int value) {
    // Start traversal from the root
    Node temp = root;
    while (temp != null) {
        // If the searched value is less than the current node's value, go left
        if (value < temp.value) {
            temp = temp.left;
        } 
        // If greater, go right
        else if (value > temp.value) {
            temp = temp.right;
        } 
        // Value is found!
        else {
            return true;
        }
    }
    // If we reached here, the value is not in the tree
    return false;
}

Inserting & Searching: The Recursive Approach

Recursion offers a clean, concise way to implement both the insertion and search functionalities. Here's a look at how we can utilize recursive strategies for these operations:

// Recursive helper function to check if a value exists in the BST
private boolean rContains(Node currentNode, int value) {
    // Base case: If node is null, value is not present
    if (currentNode == null) {
        return false;
    }
    // If the value matches the current node's value, it's found
    if (value == currentNode.value) {
        return true;
    }
    // Recursively check left or right subtree based on the value
    return value < currentNode.value ? rContains(currentNode.left, value) : rContains(currentNode.right, value);
}

// Public function that initiates the recursive search from the root
public boolean rContains(int value) {
    return rContains(root, value);
}

// Recursive function to insert a value into the BST
private Node rInsert(Node currentNode, int value) {
    // Base case: If node is null, create and return a new node with the value
    if (currentNode == null) {
        return new Node(value);
    }
    // Depending on the value, recursively insert into left or right subtree
    if (value < currentNode.value) {
        currentNode.left = rInsert(currentNode.left, value);
    } else if (value > currentNode.value) {
        currentNode.right = rInsert(currentNode.right, value);
    }
    // Return the (potentially updated) current node
    return currentNode;
}

// Public function that initiates the recursive insert from the root
public void rInsert(int value) {
    if (root == null) {
        root = new Node(value);
    } else {
        rInsert(root, value);
    }
}

Deletion: The Finer Details

Deleting a node from our BST requires careful consideration. We need to account for various scenarios:

The node has no children (a leaf node).
The node has one child.
The node has two children.

This method, as you'll see, handles all these cases.

// Function to find the node with the minimum value in a BST, used in the delete function
public int minValue(Node currentNode) {
    // Traverse left as far as possible to find the minimum value
    while (currentNode.left != null) {
        currentNode = currentNode.left;
    }
    return currentNode.value;
}

// Recursive function to delete a node with a given value from the BST
private Node deleteNode(Node currentNode, int value) {
    // Base case: If node is null, return null
    if (currentNode == null) return null;

    // Recursive delete in left or right subtree based on the value
    if (value < currentNode.value) {
        currentNode.left = deleteNode(currentNode.left, value);
    } else if (value > currentNode.value) {
        currentNode.right = deleteNode(currentNode.right, value);
    } 
    // Found the node to be deleted
    else {
        // Node with only one child or no child
        if (currentNode.left == null) return currentNode.right;
        if (currentNode.right == null) return currentNode.left;

        // Node with two children; get the inorder successor (smallest value in the right subtree)
        currentNode.value = minValue(currentNode.right);
        // Delete the inorder successor
        currentNode.right = deleteNode(currentNode.right, currentNode.value);
    }
    return currentNode;
}

// Public function that initiates the recursive delete from the root
public void deleteNode(int value) {
    root = deleteNode(root, value);
}

And that, dear readers, wraps up our introduction to constructing a Binary Search Tree in Java. Building from the ground up gives us a deeper appreciation of the intricacies involved and the mechanics of BSTs.

Stay tuned for more posts where we dive even deeper into the world of data structures and algorithms. Until then, keep coding!

Recursion in Binary Search Trees: Java Edition