Search, Insert, and Delete in Java

Welcome to Module 5! So far, we know what a BST is and how to traverse it. Now, we'll learn how to bring it to life by adding, finding, and removing data. This module is all about implementing the three core BST operations: Search, Insert, and Delete.

Mastering these algorithms is crucial, as they demonstrate the practical power of the BST and its famous O(log n) average time complexity.

1. The Search Operation – Finding a Value

Searching for a value in a BST is the most intuitive operation. The ordered nature of the tree acts as a guide, telling us exactly where to look next. It's like searching for a word in a dictionary; you instantly know whether to look forwards or backwards.

The Algorithm:

1. Start at the root.
2. Compare the target value with the current node's data.
3. If it's a match, you're done! The value exists.
4. If the target is less than the current node's data, you know it can only be in the left subtree. Move to the left child.
5. If the target is greater than the current node's data, you know it can only be in the right subtree. Move to the right child.
6. If you reach a null node, the value is not in the tree.

Java Code for BST Search:

public boolean search(TreeNode root, int value) {

// Base Case 1: The tree is empty or we've reached a dead end.

if (root == null) {

return false;

}

// Base Case 2: We found the value!

if (root.data == value) {

return true;

}

// Recursive Step: Decide whether to go left or right

if (value < root.data) {

return search(root.left, value);

} else {

return search(root.right, value);

}

}

2. The Insert Operation – Adding a New Node

Inserting a new node into a BST must be done carefully to preserve the BST property. The process is simple: we first search for where the node should be, and once we find an empty spot (null), we place the new node there. A new node is always inserted as a leaf.

The Algorithm:

1. Traverse the tree as if you are searching for the value to insert.
2. If you find a null link where the value should go, create the new node and attach it.
3. If the tree is empty, the new node becomes the root.

Java Code for BST Insert:

This recursive function returns a TreeNode so we can link the newly created node back to its parent.

public TreeNode insert(TreeNode root, int value) {

// Base Case: If the tree or subtree is empty, create the new node here.

if (root == null) {

return new TreeNode(value);

}

// Recursive Step: Decide where to insert the new node.

if (value < root.data) {

root.left = insert(root.left, value);

} else if (value > root.data) {

root.right = insert(root.right, value);

}

// If value is already in the tree, do nothing.

return root;

}

3. The Delete Operation – The Tricky Part

The delete operation in a BST is the most complex because we must ensure the BST property is maintained after the node is removed. We handle this by considering three distinct cases.

Case 1: The node to delete is a leaf node.

This is the easiest case. We can simply remove the node by setting its parent's reference to null.

Case 2: The node to delete has one child.

This is also straightforward. We "bypass" the node by linking its parent directly to its child.

Case 3: The node to delete has two children.

This is the most complex scenario. We can't just remove the node, as it would leave two disconnected subtrees.

The Strategy:

1. Find a replacement for the node. The best replacement is its inorder successor (the smallest node in its right subtree).
2. Copy the value of the inorder successor to the node we want to delete.
3. Now we have a duplicate value in the tree. Recursively call delete on the right subtree to remove the inorder successor node (which will now fall into Case 1 or 2).

Java Code for BST Delete:

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 {

// Node found! Now, handle the 3 cases.

// Case 1: Node is a leaf or has one child

if (root.left == null) {

return root.right;

} else if (root.right == null) {

return root.left;

}

// Case 3: Node has two children

// Find the inorder successor (smallest value in the right subtree)

root.data = findMinValue(root.right);

// Delete the inorder successor from the right subtree

root.right = delete(root.right, root.data);

}

return root;

}

// Helper function to find the minimum value in a tree (the leftmost leaf)

private int findMinValue(TreeNode root) {

int minValue = root.data;

while (root.left != null) {

minValue = root.left.data;

root = root.left;

}

return minValue;

}

Let's do it. Module 6 is all about connecting the dots from the code we've written to the real-world technology it powers. This section is designed to be inspiring and show the practical importance of mastering trees.