I think there is a missing scenario about deletion of a parent node with 2 children.
When the right subtree’s smallest element is also a parent. Which means that right subtree’s top element doesn’t have left child.
In the above case, after step #2 of deletion algorithm, the replaced node (soon-to-be deleted) is a parent node with one child instead of a leaf node.
After this step, it will be handled as a deletion of a parent node with 1 child.
Hope i made myself clear.
Hi @Anil_Bhaskar,
Thank you so much for reaching out to us.
boolean delete(int value, Node currentNode) {
if (root == null) { // for empty list
return false;
}
Node parent = null; //To Store parent of currentNode
while(currentNode != null && (currentNode.getData() != value)) { // finding the node to be deleted
parent = currentNode;
if (currentNode.getData() > value)
currentNode = currentNode.getLeftChild();
else
currentNode = currentNode.getRightChild();
}
if(currentNode == null) {
return false;
}
else if(currentNode.getLeftChild() == null && currentNode.getRightChild() == null) { //if the node is a leaf node
//if that leaf node is the root (a tree with just root)
if(root.getData() == currentNode.getData()){
setRoot(null);
return true;
}
else if(currentNode.getData() < parent.getData()){
parent.setLeftChild(null);
return true;
}
else{
parent.setRightChild(null);
return true;
}
} else if(currentNode.getRightChild() == null) { // for node having a single child on left
if(root.getData() == currentNode.getData()){
setRoot(currentNode.getLeftChild());
return true;
}
else if(currentNode.getData() < parent.getData()){
parent.setLeftChild(currentNode.getLeftChild());
return true;
}
else{
parent.setRightChild(currentNode.getLeftChild());
return true;
}
}
else if(currentNode.getLeftChild() == null) { // for node having a single child on right
if(root.getData() == currentNode.getData()){
setRoot(currentNode.getRightChild());
return true;
}
else if(currentNode.getData() < parent.getData()){
parent.setLeftChild(currentNode.getRightChild());
return true;
}
else{
parent.setRightChild(currentNode.getRightChild());
return true;
}
}
else { // for node having 2 children
//Find Least Value Node in right-subtree of current Node
Node leastNode = findLeastNode(currentNode.getRightChild());
//Set CurrentNode's Data to the least value in its right-subtree
int temp = leastNode.getData();
delete(temp, root);
currentNode.setData(temp);
//Delete the leafNode which had the least value
return true;
}
}
The above code in which delete(temp, root); is a recursive call to the delete() which we are implementing and we have already coded how deal with the situation in the above if-else statements which will delete any node which has one child or a leaf node. So, we don’t have to worry about removing any node having any child or not.
If there is any confusion then please do let me know. Thanks.