In this tutorial we will learn how to Delete Node in BST(Binary Search Tree) with example. The example below deletes a node from the BST, See full example below.
What is Binary Search Tree?
A Binary Search Tree is a node-based binary data structure which has some properties those are below:
- Left subtree nodes always be less than the root node.
- Right subtree nodes always be greater than the root node.
- Left and right subtree also Binary Search Tree.
- By default there is no duplicate.
Example To Delete Node in BST
See the full example below to delete node from Binary Search Tree.
There can be tree case to delete a node, consider these before any node.
1. Node to be deleted is the leaf.
Simply remove it from the node tree.
2. Node to be deleted has only one child.
Copy the child to the node and delete the node.
3. Node to be deleted has two children.
To delete the node in this case you have to find the inorder successor of the node. Copy content of the inorder successor to the node and delete the inorder successor.
Code
public class BinaryTreeBT {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// creating binary search tree
public static Node createBST(Node root, int val) {
if (root == null) {
root = new Node(val);
return root;
}
if (root.data > val) {
root.left = createBST(root.left, val);
} else {
root.right = createBST(root.right, val);
}
return root;
}
// delete a node in bst
public static Node deleteNode(Node root, int key){
if(root == null){
return null;
}
if(key < root.data){
root.left = deleteNode(root.left, key);
}else if(key > root.data){
root.right = deleteNode(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 child get the inorder successor(smallest in the right subtree)
Node IS = inOrderSuccessor(root.right);
root.data = IS.data;
// delete the inorder successor
root.right = deleteNode(root.right, IS.data);
}
return root;
}
public static Node inOrderSuccessor(Node root){
while (root.left != null) {
root = root.left;
}
return root;
}
public static void main(String[] args) {
int[] values = {12, 8, 10, 1, 3, 4, 6, 9, 15};
Node root = null;
// creating binary search tree
for(int i=0; i<values.length; i++){
root = createBST(root, values[i]);
}
// delete a key in bst
root = deleteNode(root, 4);
System.out.println("new root Node = " + root.data);
}
}
Output: The deleted node will removed from the BST as shown in the below graph. You can see more from Here.
Thank you for reaching out this tutorial. For any doubt and query, you can comment in the comments section below.
How To Post Free?
You can post your content here free, without any cost. Just create account then start posting or you can mail to [email protected].
