Deletion In Binary Search Tree In Java
Deletion In Binary Search Tree
Here you will learn about Deletion in Binary search tree in java programming language.
A Binary Search Tree is a rooted binary tree whose internal nodes each a key greater than all the keys in the node’s left subtree and less than those in it’s right subtree. Delete function is used to delete the specified node from binary search tree. In this article we will perform deletion in binary search tree.
Deletion In Binary Search Tree In Java
Why is Deletion Important?
Deletion is required when:
- Removing outdated or unnecessary data
- Maintaining dynamic datasets
Implementing real world systems like:
- Database indexing
- File systems
- Memory management
There are 3 possible cases in Deletion in BST:
Deleting a node with no children
Deleting a node with two children
Deleting a node with no child
Case 1: Deleting a node with no children:
If the node to be deleted from the tree has no child nodes, the node is simple deleted from the tree since it is a leaf node.
Case 2: Deleting a node with two children:
we first find the inorder predecessor of the node and replace the target node with the inorder predecessor.
Case 3: Deleting a node with one child:
If the node to be deleted has a single child node, the target node is replaced from its child node and then the target node is simply deleted.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Algorithm for Deletion In Binary Search Tree
- If root is null → return null
- If key < root → go left
- If key > root → go right
- If key == root:
If no child → return null
If one child → return that child
If two children:
Find minimum value in right subtree
Replace root value
Delete that value from right subtree
- Return root
Java Code for Deletion In Binary Search Tree
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class BSTDeletion {
// Insert function (for building tree)
public static Node insert(Node root, int key) {
if (root == null) return new Node(key);
if (key < root.data)
root.left = insert(root.left, key);
else if (key > root.data)
root.right = insert(root.right, key);
return root;
}
// Find minimum value node
public static Node findMin(Node root) {
while (root.left != null) {
root = root.left;
}
return root;
}
// Delete function
public static Node delete(Node root, int key) {
if (root == null) return null;
// Traverse the tree
if (key < root.data) {
root.left = delete(root.left, key);
}
else if (key > root.data) {
root.right = delete(root.right, key);
}
else {
// Case 1: No child
if (root.left == null && root.right == null) {
return null;
}
// Case 2: One child
else if (root.left == null) {
return root.right;
}
else if (root.right == null) {
return root.left;
}
// Case 3: Two children
Node successor = findMin(root.right);
root.data = successor.data;
root.right = delete(root.right, successor.data);
}
return root;
}
// Inorder traversal
public static void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
public static void main(String[] args) {
Node root = null;
// Build BST
int[] values = {10, 5, 15, 2, 7, 12};
for (int val : values) {
root = insert(root, val);
}
System.out.print("Before Deletion: ");
inorder(root);
// Delete node
root = delete(root, 10);
System.out.print("\nAfter Deletion: ");
inorder(root);
}
}
Input
Insert: 10, 5, 15, 2, 7, 12 Delete: 10
Output
Before Deletion: 2 5 7 10 12 15 After Deletion: 2 5 7 12 15
Worst Case: O(n)
h = height of tree
Frequently Asked Questions
Answer:
It is the process of removing a node from a BST while maintaining its ordered structure.
Answer:
There are three cases: leaf node, node with one child, and node with two children.
Answer:
It replaces the node with its inorder successor or predecessor and then deletes that node.
Answer:
It is O(log n) in balanced trees and O(n) in skewed trees.
Answer:
Yes, but recursive approach is simpler and more commonly used.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment