How to delete a Node in a Binary Search Tree

Share

Deleting a node in a given Binary Search Tree is a process to delete any existing node; let’s say if node A has to be deleted then you got to follow below steps –

STEP 1: If there is no node in a given BST then return saying node A can not be deleted as there is no node in the BST.

STEP 2: Find Node A in a given Binary Search Tree which we need to delete. To find so, just compare the value of node A with the root node’s value: 

if node A has a value greater than the root node’s value – traverse down the root node in its right node and Go to Step 2 by considering this right node as the root node (Note: if there is no right node straight go to Step 3)

if node A has a value lesser than the root node’s value – traverse down the root node in its left node and Go to Step 2 by considering this left node as the root node (Note: if there is no left node straight go to Step 3)

if node A has a equal to the root node’s value – it just means you have found the node which is to be deleted from the tree – You got to delete this node and to do so just Go to Step 4

STEP 3: Just return saying node A can not be deleted as it is not present in the BST.

STEP 4: Once the Node to be deleted is found using step 2: three cases may arise –

case 1: this node has no children [ in this case – just assign null to the parent of this node – You are done deleting the node ]

case 2: this node has only one Child [ in this case – just assign this node’s right child or left child reference whichever it has to the parent of this node – You are done deleting the node ]

case 3: this node has both the children [ In this case – just replace this node with its in order successor node followed by deleting in order successor from its original position in the BST ]

Above Algorithm can be implemented using two popular ways – Recursive and an Iterative way

BST,java


package org.gontuseries.bst;

public class BST {

    private Node rootNode;

        public void delete(int value) {

        rootNode = delete(value, rootNode);
    }

    private Node delete(int value, Node currentNode) {

        if (currentNode == null) {
            System.out.println("Value to be deleted is not present in the BST");
            return null;
        }

        if (value > currentNode.getValue()) {

            currentNode = delete(value, currentNode.getRightNode());
        } else if (value < currentNode.getValue()) {

            currentNode = delete(value, currentNode.getLeftNode());
        } else {

            if (currentNode.getLeftNode() == null
                          && currentNode.getRightNode() == null) {
                return null;
            } else if (currentNode.getLeftNode() == null) {
                return currentNode.getRightNode();
            } else if (currentNode.getRightNode() == null) {
                return currentNode.getLeftNode();
            } else {
                currentNode.
                    setValue(getSuccessorNodeValue(currentNode.getRightNode()));
                delete(currentNode.getValue(), currentNode.getRightNode());
            }
        }

        return currentNode;
    }

    private int getSuccessorNodeValue(Node currentNode) {

        while (true) {
            if (currentNode.getLeftNode() != null) {

                currentNode = currentNode.getLeftNode();
            } else {
                break;
            }
        }

        return currentNode.getValue();
    }

    private Node createNewNode(int value) {

        Node node = new Node(value);

        return node;
    }
}

package org.gontuseries.bst;

public class BST {

    private Node rootNode;

    private void delete(int value) {

        if (rootNode == null) {
            System.out.println("There are no nodes in this Binary Search Tree");
        } else {

            Node currentNode = rootNode;
            Node parentNode = null;

            while (true) {

                if (value > currentNode.getValue()) {

                    if (currentNode.getRightNode() != null) {

                        parentNode = currentNode;
                        currentNode = currentNode.getRightNode();
                    } else {

                        System.out.println("No Node is present with this value");
                        break;
                    }
                } else if (value < currentNode.getValue()) {

                    if (currentNode.getLeftNode() != null) {

                        parentNode = currentNode;
                        currentNode = currentNode.getLeftNode();
                    } else {

                        System.out.println("No Node is present with this value");
                        break;
                    }
                } else {

                    if (currentNode.getLeftNode() == null
                                            && currentNode.getRightNode() == null) {
                        if (parentNode == null) {
                            rootNode = null;
                        } else if (parentNode.getLeftNode().getValue() == currentNode.getValue()) {

                            parentNode.setLeftNode(null);
                        } else {
                            parentNode.setRightNode(null);
                        }
                    } else if (currentNode.getLeftNode() == null) {
                        if (parentNode == null) {
                            rootNode = currentNode.getRightNode();
                        } else if (parentNode.getLeftNode().getValue() == currentNode.getValue()) {

                            parentNode.setLeftNode(currentNode.getRightNode());
                        } else {
                            parentNode.setRightNode(currentNode.getRightNode());
                        }
                    } else if (currentNode.getRightNode() == null) {
                        if (parentNode == null) {
                            rootNode = currentNode.getLeftNode();
                        } else if (parentNode.getLeftNode().getValue() == currentNode.getValue()) {

                            parentNode.setLeftNode(currentNode.getLeftNode());
                        } else {
                            parentNode.setRightNode(currentNode.getLeftNode());
                        }
                    } else {
                        int successorNodeValue = getSuccessorNodeValue(currentNode.getRightNode());
                        delete(successorNodeValue);
                        currentNode.setValue(successorNodeValue);
                    }
                }
            }
        }    
    }

    private int getSuccessorNodeValue(Node currentNode) {

        while (true) {
            if (currentNode.getLeftNode() != null) {

                currentNode = currentNode.getLeftNode();
            } else {
                break;
            }
        }

        return currentNode.getValue();
    }

    private Node createNewNode(int value) {

        Node node = new Node(value);

        return node;
    }
}

Node.java


package org.gontuseries.bst;

public class Node {

    Node(int value) {
        this.value = value;
        this.leftNode = null;
        this.rightNode = null;
    }

    private int value;
    private Node leftNode;
    private Node rightNode;
    // --- writing all getters and setters for all properties 
    //i.e for value, leftNode, rightNode
}

Time Complexity: The run time complexity of delete operation using Recursive way is: O(height of a Binary Search Tree) i.e O(h) [worst-case]

a) In case of a  skewed Binary Search Tree the height is equal to the number of nodes in it; so, it becomes O(n)[worst-case]

b) In case of a Binary Search Tree built using some Tree Balancing Techniques like AVL, RED Black etc the height is equal to log (number of nodes in it); so it becomes log(n) [worst-case]

where, ‘n’ is the number of nodes in a binary search tree.