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!