CODEWITHSUNDEEP
data-structuresbinary-search-tree
Mendax
Mendax

Reputation: 47

Not Returning the deleted node from Binary Search Tree

The following program deletes node from Binary Search Tree, however, it doesn't return the deleted node for some reason, it only returns the root node. The following delete() function does delete the value Here is the following code,

#Binary Node Class
class BinaryNode {
    int info;
    BinaryNode left;
    BinaryNode right;

    public BinaryNode(int info){
        this.info = info;
        left = null;
        right = null;
    }

    public void displayNode(){
        System.out.print(this.info);
    }
}

//Binary Tree Operation Class

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class BinaryTreeOperations{

    BinaryNode rootNode;

    public BinaryTreeOperations(){
        rootNode = null;
        rootNode = insertTreeNodes(rootNode, 7); //root node
        insertTreeNodes(rootNode, 4); // inserts the next following elements in BST ordered.
        insertTreeNodes(rootNode, 1);
        insertTreeNodes(rootNode, 8);
        insertTreeNodes(rootNode, 10);
        insertTreeNodes(rootNode, 2);
        insertTreeNodes(rootNode, 21);
        insertTreeNodes(rootNode, 5);

        inOrderTraversal(rootNode);

        System.out.print("Deleted Node: " );
        delete(rootNode, 8).displayNode();
        System.out.println();
        inOrderTraversal(rootNode);
    }

    public BinaryNode delete(BinaryNode root, int key){
        if(root == null)
            return root;
        if(key < root.info)
            root.left = delete(root.left, key);
        else if(key > root.info)
            root.right = delete(root.right, key);
        else{
            if(root.left != null && root.right != null){
                root.info = findMin(root.right).info;
                root.right = delete(root.right, root.info);
            }
            else
                root = (root.left != null) ? root.left : root.right;
        }
        return root;
    }

    private BinaryNode findMin(BinaryNode root) {
        if(root != null){
            while(root.left != null){
                root = root.left;
            }
        }
        return root;
    }

    public void inOrderTraversal(BinaryNode root){
        if(root == null)
            return;
        else{
            inOrderTraversal(root.left);
            root.displayNode();
            System.out.print(", ");
            inOrderTraversal(root.right);
        }
    }

    //Recursively, adds a node inside a tree using binary search tree concept.

    /**
     * BST -> puts the small number on the left subtrees from the root node and puts the large numbers on the right subtree.
     * @param root -> root node of the tree.
     * @param data -> data that's to be added in the tree.
     * @return -> returns BinaryNode which contains the info of data, left and right subtree's location.
     */

    public BinaryNode insertTreeNodes(BinaryNode root, int data){

        if(root == null) {
            root = new BinaryNode(data);
            root.left = root.right = null;
        }
        else if(data <= root.info)
            root.left = insertTreeNodes(root.left, data);
        else
            root.right = insertTreeNodes(root.right, data);
        /*System.out.println(root + " " + root.left + " " + root.right);*/
        return root;
    }

    public static void main(String[] args) {
        BinaryTreeOperations treeOperation = new BinaryTreeOperations();
    }
}

Output:
1, 2, 4, 5, 7, 8, 10, 21,
Deleted Node: 7
1, 2, 4, 5, 7, 10, 21,

Upvotes: 0

Views: 157

Answers (1)

trincot
trincot

Reputation: 350781

The delete function is not designed to return the deleted node. It must return the root node, as the caller uses this information to actually assign that node reference to either its left or right child. So this must never be the deleted node, as otherwise the caller would reinsert it!

Moreover, there are situations where the deleted node is not the node that originally had the value being looked for. Sometimes it is another node that is deleted instead. So then the question is, which node do you want to know about: the one that originally had the value, but got its value updated and remains present in the tree, or the node that had a different value, but was deleted instead?

If you want to have the reference of the node that really was removed from the tree -- not necessarily having the value that was to be deleted -- then you could use a member variable for the BinaryTreeOperations class, and then have it initialised at the moment a node is really skipped over -- in the last else clause:

public class BinaryTreeOperations{
    BinaryNode rootNode;
    BinaryNode lastDeleted; // <--

    // ...

    public BinaryNode delete(BinaryNode root, int key){
        // ...

            else {
                lastDeleted = root; // <--
                root = (root.left != null) ? root.left : root.right;
            }

The caller should then look at that lastDeleted member variable to have the reference to the deleted node.

Finally, I am not convinced it is good practice to get a reference to a removed node, as that will prevent the node to be garbage collected. True removal would mean you actually don't keep a reference to it.

Upvotes: 1

Related Questions