educative.io

Educative

Deletion of a parent node, when it's right subtree's smallest element is a parent too

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.

1 Like

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.