// Node class representing each element in the BST
class TreeNode {
int data;
TreeNode left, right;
public TreeNode(int data) {
this.data = data;
this.left = this.right = null;
}
}
// BST class implementing insert, search, delete, and traversals
class BinarySearchTree {
private TreeNode root;
public BinarySearchTree() {
this.root = null;
}
// Insert a new value into the BST
public void insert(int value) {
root = insertRec(root, value);
}
private TreeNode insertRec(TreeNode root, int value) {
if (root == null) {
return new TreeNode(value);
}
if (value < root.data) {
root.left = insertRec(root.left, value);
} else if (value > root.data) {
root.right = insertRec(root.right, value);
}
return root;
}
// Search for a value in the BST
public boolean search(int value) {
return searchRec(root, value);
}
private boolean searchRec(TreeNode root, int value) {
if (root == null) return false;
if (root.data == value) return true;
return value < root.data ? searchRec(root.left, value) : searchRec(root.right, value);
}
// Delete a node from the BST
public void delete(int value) {
root = deleteRec(root, value);
}
private TreeNode deleteRec(TreeNode root, int value) {
if (root == null) return null;
if (value < root.data) {
root.left = deleteRec(root.left, value);
} else if (value > root.data) {
root.right = deleteRec(root.right, value);
} else {
// Case 1: Node with one child or no child
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// Case 2: Node with two children – find inorder successor (smallest in right subtree)
root.data = minValue(root.right);
root.right = deleteRec(root.right, root.data);
}
return root;
}
private int minValue(TreeNode root) {
int minVal = root.data;
while (root.left != null) {
minVal = root.left.data;
root = root.left;
}
return minVal;
}
// Inorder traversal (Left, Root, Right) – Sorted order
public void inorder() {
inorderRec(root);
System.out.println();
}
private void inorderRec(TreeNode root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}
// Preorder traversal (Root, Left, Right)
public void preorder() {
preorderRec(root);
System.out.println();
}
private void preorderRec(TreeNode root) {
if (root != null) {
System.out.print(root.data + " ");
preorderRec(root.left);
preorderRec(root.right);
}
}
// Postorder traversal (Left, Right, Root)
public void postorder() {
postorderRec(root);
System.out.println();
}
private void postorderRec(TreeNode root) {
if (root != null) {
postorderRec(root.left);
postorderRec(root.right);
System.out.print(root.data + " ");
}
}
// Level-order traversal (BFS using queue)
public void levelOrder() {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode tempNode = queue.poll();
System.out.print(tempNode.data + " ");
if (tempNode.left != null) queue.add(tempNode.left);
if (tempNode.right != null) queue.add(tempNode.right);
}
System.out.println();
}
}
// Main class to test BST implementation
public class BSTDemo {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// Insert elements into BST
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
System.out.println("Inorder traversal (Sorted order):");
bst.inorder(); // 20 30 40 50 60 70 80
System.out.println("Preorder traversal:");
bst.preorder(); // 50 30 20 40 70 60 80
System.out.println("Postorder traversal:");
bst.postorder(); // 20 40 30 60 80 70 50
System.out.println("Level order traversal:");
bst.levelOrder(); // 50 30 70 20 40 60 80
// Search for a value
System.out.println("Search 40: " + bst.search(40)); // true
System.out.println("Search 100: " + bst.search(100)); // false
// Delete a node
bst.delete(50);
System.out.println("Inorder after deleting 50:");
bst.inorder(); // 20 30 40 60 70 80
}
}
