how to delete the nodes of the original tree? cannot delete it by passing the object reference and making it null in another method, anyway?

Question

Here is the code for a BST ,traversing in bottom-up manner and trying to delete the leaf nodes if its value is equal to "k", so if the leaves are deleted and the new leaf formed has the value "k", i am also deleting them.

So this is the reasonI i am traversing in bottom-up fashion. To delete the leaf I am just assigning the Node reference to null but which actually does not delete it because java is pass by value, is there anyway that i can make changes to the original tree in the following part of the code:

       if(l==null&&r==null&&n.k==k){
           n=null;
           return n;
       }

but after printing the tree values its showing up the same tree as before, but when I change the node value n.k=0 the values are changing, but its not taking the null reference.

Why is null not assigned to the nodes?

below is the code, running this code prints the same tree again after the **************************:

   class Node{
        Node(int k){
            this.k = k;
        }
        int k;
        Node right;
        Node left;
    }

public class Testing {
    static void preOrder(Node n){
        if(n==null);

        else{
            preOrder(n.left);
            preOrder(n.right);
            System.out.println(n.k);
        }
    }

    static Node del_leaves(Node n,int k){
       if(n==null)
           return null;
       else{
           Node l=null,r=null;
           if(n.left!=null)
               l = del_leaves(n.left,k);
           if(n.right!=null)
               r = del_leaves(n.right,k);
           if(l==null&&r==null&&n.k==k){
               n=null;
               return n;
           }
           else
               return n;
       }
    }
public static void main(String args[]){
    Node root = new Node(10);
    Node a = new Node(5);
    Node b = new Node(5);
    Node c = new Node(5);
    Node d = new Node(5);
    Node e = new Node(5);
    root.left=a;
    root.right=b;
    a.left=c;
    a.right=d;
    b.left=e;
    preOrder(root);
    Node ret_root = del_leaves(root,5);
    System.out.println("*****************************");
    preOrder(ret_root);
}

}

always use `{` and `}` for one line expressions so you can reason about their correctness! Also get rid of all those `null` checks with some better code that does not need `null` and always use `final` and do not reuse references to make it easy to reason about the values in a deterministic way for static analysis. — , Aug 29 '15 at 07:21
It's not a standard approach to have multiple nodes with the same value in BST. If you decide to have only one node with given value (doing nothing upon insert if there's a node with given value) your problem will disappear. This is also in line with your removal logic which is removing all instances for given value. — MirMasej, Aug 29 '15 at 07:25
@MirMasej ,yes BST shouldnt have duplicates by definition, but this question is asked in microsoft interview exam to me. my problem is how to delete the nodes in the original tree. thank you — murali kurapati, Aug 29 '15 at 09:19

score 2 · Answer 1 · answered Aug 29 '15 at 07:20

2

Java is always call by value. You gets a copy of the reference in Node n. So n=null won't change the reference in the calling context. Only the local reference variable n is set to null.

answered Aug 29 '15 at 07:20

PeterMmm

24,152
13
73
111

score 1 · Accepted Answer · edited May 23 '17 at 12:00

1

Since you cannot change the node n, you wisely return the value that it should have been - either null or its old value depending on whether it was deleted or not.

The problem is that you are not using that returned value, and therefore you lose that advantage.

Use the returned value to assign the new left and right to your tree:

       if(n.left!=null)
           n.left = del_leaves(n.left,k);
       if(n.right!=null)
           n.right = del_leaves(n.right,k);
       if(n.left ==null && n.right==null && n.k==k){
           return null;
       }
       return n;

As for the reason why assigning directly to n doesn't work, as PeterMmm said, Java is pass by value. For an extended discussion of that, including some nice answers with drawings, please refer to this question: Is Java "pass-by-reference" or "pass-by-value"?.

edited May 23 '17 at 12:00

Community

1
1

answered Aug 29 '15 at 07:28

RealSkeptic

33,993
7
53
79

but i want to make that node pointing to null, that is ,i want to make changes to the tree. to be explicit i want to delete that node. – murali kurapati Aug 29 '15 at 08:57
@MuraliKrish The node will be deleted because you return `null`, and that `null` will be assigned to the `n.right` or `n.left` in the higher level of recursion. It's the only way you can change the tree - you cannot assign a `null` to `n` because it is a local variable. You can only change its fields. – RealSkeptic Aug 29 '15 at 10:02

how to delete the nodes of the original tree? cannot delete it by passing the object reference and making it null in another method, anyway?

2 Answers2