import java.util.
Random;
class TreeNode {
int key;
TreeNode left, right;
public TreeNode(int item) {
key = item;
left = right = null;
}
}
public class BinarySearchTree {
private TreeNode root;
public BinarySearchTree() {
root = null;
}
// In-order traversal
public void inOrderTraversal() {
inOrderTraversal(root);
System.out.println();
}
private void inOrderTraversal(TreeNode root) {
if (root != null) {
inOrderTraversal(root.left);
System.out.print(root.key + " ");
inOrderTraversal(root.right);
}
}
// Insert a key into the BST
public void insert(int key) {
root = insert(root, key);
}
private TreeNode insert(TreeNode root, int key) {
if (root == null) {
return new TreeNode(key);
}
if (key < root.key) {
root.left = insert(root.left, key);
} else if (key > root.key) {
root.right = insert(root.right, key);
}
return root;
}
// Remove a key from the BST
public void remove(int key) {
root = remove(root, key);
}
private TreeNode remove(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key < root.key) {
root.left = remove(root.left, key);
} else if (key > root.key) {
root.right = remove(root.right, key);
} else {
// Node with only one child or no child
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}
// Node with two children, get the in-order successor (smallest in the
right subtree)
root.key = minValue(root.right);
// Delete the in-order successor
root.right = remove(root.right, root.key);
}
return root;
}
private int minValue(TreeNode root) {
int minValue = root.key;
while (root.left != null) {
minValue = root.left.key;
root = root.left;
}
return minValue;
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// Insert keys 1 to 15
int[] keys = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
for (int key : keys) {
bst.insert(key);
}
// Display keys using in-order traversal
System.out.print("Tree after insertion: ");
bst.inOrderTraversal();
// Remove key 5
bst.remove(5);
System.out.print("Tree after removing key 5: ");
bst.inOrderTraversal();
// Remove key 15
bst.remove(15);
System.out.print("Tree after removing key 15: ");
bst.inOrderTraversal();
// Remove key 1
bst.remove(1);
System.out.print("Tree after removing key 1: ");
bst.inOrderTraversal();
// Insert key 2
bst.insert(2);
System.out.print("Tree after inserting key 2: ");
bst.inOrderTraversal();
}
}
