CODEWITHSUNDEEP
javatree
mastash3ff
mastash3ff

Reputation: 312

Removal of leaves in a binary tree

I'm confused on why my removal method of leaves in a BST is not working. If I assign 0 to the data, its reflected in the tree, but when I assign null to the node, it's still able to be referenced in the BST traversal. 

public void removeLeaves(){
    removeLeaves(getRoot());
}

private void removeLeaves(IntTreeNode node) {
    if (node == null)
        return;
    else if( node.left == null && node.right == null){
        node.data = 0;  //im finding the leave nodes correctly
        node = null;    //but its not removing them
    }
    else {
        removeLeaves(node.left);
        removeLeaves(node.right);
    }
}

        overallRoot
        ____[7]____
       /           \
    [3]             [9]
   /   \           /   \
[0]     [0]     [0]     [8]
                           \
                            [0]

Could somebody explain why this is not working as intended?

Upvotes: 3

Views: 384

Answers (2)

mastash3ff
mastash3ff

Reputation: 312

public void removeLeaves () {
    if (getRoot() != null) 
        removeLeaves (getRoot());
}

private IntTreeNode removeLeaves (IntTreeNode node) {
    if (getRoot().left == null && getRoot().right == null) {
        setRoot(null);
    } else {
        if (node.left != null) {
            if (node.left.left == null && node.left.right == null) 
                node.left = null;             
            else 
                removeLeaves(node.left);
        }
        if (node.right != null) {
            if (node.right.right == null && node.right.left == null) 
                node.right = null;      
            else 
                removeLeaves(node.right);     
        }
    }
    return node;
}

Upvotes: 0

Karthik
Karthik

Reputation: 5040

In your example tree , consider 9

 9.left => null
 9.right => address of 8

when you assign node.data = 0; , node has address of 8 so 0 will be reflected in the tree.

But when you do node =null, you are just changing the variable node. you are not doing any operation on address of 8.

I think what you are hoping to happen is by doing node = null is:

      address of 8 = null

which is actually not possible, because you are just changing the variable node.

Say address of 8 is 0XABCD, so node = 0XABCD. when you do node.data=0 as node has address 0XABCD, 0XABCD.data will be changed to 0. but when you do node = null, you are just assigning a new value to a variable node, you are not doing any operation on the original address 0XABCD.

What you actually have to do is

  if(node.left!= null && node.left.left == null && node.left.right ==null)
     node.left =null

  if(node.right!= null && node.right.left == null && node.right.right ==null)
     node.right =null

UPDATE

What you are trying to do is something like this:

  Foo foo = new Foo();
  Foo anotherFoo = foo;

  anotherFoo.value = something; // both foo.value and anotherFoo.value will be changed to "something", because of the reference.

  anotherFoo = null; 
  // here you are expecting foo also to be null which is not correct.

Upvotes: 4

Related Questions