2

i was trying to delete the minimum element in BST. there can be 2 cases:

Case I: right child not present In that case, set current node to null straight away.

node=delete(node);

Case II: right child present. In that case copy the contents of right child to current node and delete the right child.

if(node.right!=null)
        {
            node.data=node.right.data;
            node.right=null;
        }

My doubt is, why does the second case work and the first doesnt. I mean, if "node" is a reference variable and so nulling it doesnt make it null in actual tree, then WHY does node.right works just fine? My full code of the function:

public static int del_min(Node node)
{
    if(node.left==null)
    {
        minimum=node.data;
        if(node.right!=null) //WORKING
        {
            node.data=node.right.data;
            node.right=null;
        }
        else //NOT WORKING
        {
            node=null;
        }
    }
    else
    {
        minimum=del_min(node.left);
    }
    return minimum;
}

Please help me.

Nidhi Sharma
  • 33
  • 5

1 Answers1

1

The reason this doesn't work is because the node.right is stored in memory whereas node is a temporary pointer to a location in memory.

What this means is that when you update node.right you will actually lookup a stored pointer in permanent memory and then change it. When you update node, it will only update it in the stack frame and that reference is chucked away anyway when the function has finished execution.

Here is some more information about pass by reference and reference types in general: https://web.archive.org/web/20180706164632/http://www.yoda.arachsys.com/csharp/parameters.html

silleknarf
  • 1,219
  • 6
  • 22