dnc123 dnc123 - 11 days ago 5
Java Question

Setting reference object key to null doesn't work as expected

I need to remove the smallest value of binary search tree but I can't find a clean way to do it, currently I have kind of clean code, though it doesn't work as I expect it to work, I've got this code(MTE got MTE left, MTE right and int val keys):

MTE tempElement = root;

if(root == null) return;
else if((root.left == null) && (root.right == null))
{
root = null;
return;
}
else if(root.left != null)
{
while(tempElement.left != null) tempElement = tempElement.left;

if(tempElement.right == null) tempElement = null;
else tempElement = tempElement.right;
}
else if(root.right != null)
{
if(tempElement.left == null) root = tempElement;
else
{
while(tempElement.left != null) tempElement = tempElement.left;

root.val = tempElement.val;
if(tempElement.right == null) tempElement = null;
else tempElement = tempElement.right;
}
}


The problem I got with this code is when I get to this line of code -
if(tempElement.right == null) tempElement = null;
Which is 13th line on the code snippet that I provided. When I debugged it it changes tempElement to null, but my main root element doesn't change any of its nodes - the way I expected it to work, any workaround?

Answer

You should hold pointer to the parent node and then change the parent node's left or right pointer, for example

if(root.left != null)
{
    MTE prev = tempElement;
    while(tempElement.left != null) {
         prev = tempElement;
         tempElement = tempElement.left;
    }

    if(tempElement.right == null)  prev.left = null;
    else prev.left = tempElement.right;
}

Need to do the same for right != null as well.

Comments