public class DeleteFromBST {
public static void main(String[] args) {
int[] arr = {5,3,8,2,1,6,7,4,9};
Node root = null;
for(int val:arr) {
root = insertNode(root, val);
}
Node node= removeNode(root, 5);
printInorder(node);
}
static Node removeNode(Node root, int key) {
if(null!=root) {
if(key<root.value) {
root.left = removeNode(root.left, key); //if key small then current node then recursion for left
}else if(key>root.value) {
root.right = removeNode(root.right, key);//if key small then current node then recursion for right
}else {
//check how many nodes after found current node
//if only one child at key node or no child
if(root.left==null) {
return root.right;
}else if(root.right==null) {
return root.left;
}
//if 2 child at key node
//pass right
root.value = findMin(root.right);//replace key node with min node
root.right = removeNode(root.right, root.value);//remove duplicate min node from right as in previous step we hvae find min node from right
}
}
return root;
}
static int findMin(Node node) {
//find min till all left node end due to inorder successor rule
int min = node.value;
while(null!=node.left) {
if(min>node.left.value) {
min = node.left.value;
node = node.left;
}
}
return min;
}
static void printInorder(Node node) {
if(null!=node) {
printInorder(node.left);
System.out.println(node.value);
printInorder(node.right);
}
}
static Node insertNode(Node root, Integer value) {
Node newNode = new Node(value);
if (root == null) {
return newNode;
} else {
if (value <= root.value) {
root.left = insertNode(root.left, value);
} else {
root.right = insertNode(root.right, value);
}
return root;
}
}
static class Node{
Integer value;
Node left;
Node right;
Node(Integer value){
this.value = value;
left = right = null;
}
}
}
ref: https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/
No comments:
Post a Comment