Removing leaves in a binary tree
I am confused as to why my method of removing leaves in BST is not working. If I assign 0 to the data it is reflected in the tree, but when I assign null to the node value, it can still refer to 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]
Can someone explain why this is not working as intended?
source to share
In the example tree, consider 9
9.left => null
9.right => address of 8
when you assign the node.data = 0;
node has an address 8
, so 0
will show up in the tree.
But when you do node =null
, you just change the variable node
. you are not performing any operations on address of 8
.
I think what you are hoping for is node = null
:
address of 8 = null
which is actually not possible, because you are just changing the variable node
.
Let's say the address 8
is equal 0XABCD
, therefore node = 0XABCD
. when you execute node.data=0
since it node
has an address 0XABCD
, 0XABCD.data
will be changed to 0
. but when you do node = null
, you are just assigning a new value to the variable node
, you are not performing any operations on the original address 0XABCD
.
Actually you need
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 looks 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.
source to share
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;
}
source to share