Unable to set reference variable in recursive call

Question

I am using a recursive method to find a node in a binary tree using a key. When I find the node, I set it to my reference variable foundNode and return. The problem is that when I read the object its value is still null. Can anybody help?

findGivenNode(root, key, foundNode, parentStack);

private boolean findGivenNode(Node node, int key, Node foundNode, Stack<Node> parentStack) {
    if (node == null) {
        return false;
    }

    parentStack.add(node);
    if (node.getData() == key) {
        foundNode = node;
        return true;
    }  
    boolean leftReturn = findGivenNode(node.getLeftChild(), key, foundNode, parentStack);
    boolean RightReturn = findGivenNode(node.getRightChild(), key, foundNode, parentStack);        
    if (leftReturn || RightReturn) {
        return true;
    }  else {
        parentStack.pop();
        return false;
    }
}

score 3 · Accepted Answer · edited May 23 '17 at 12:08

Java doesn't pass arguments by reference, they are passed by value. Read more here

Let's clarify by an example. Make the key you are looking for be integer with value 21. The situation at the beginning of the function is the following:

initial_state

So now, when you say:

foundNode = node; // this doesn't reflect outside of the method

You are changing the value of foundNode locally inside the findGivenNode() method, it doesn't apply to outside this method. Basically, the local variable called foundNode references the node you want to change and then you make this local variable foundNode reference the new node by the statement above. This change is reflected only inside the function. As soon as your function is finished, local variables don't exist anymore so neither does this local version of foundNode. Visual result:

wrong_move

The simple solution is to use a Wrapper function

To keep track of the reference, you can make a simple wrapper class that will store the reference you want:

private class NodeWrapper {
    Node foundNode;
    NodeWrapper() {
        foundNode = null;
    }
}

Then you can create a new NodeWrapper and pass that into your function instead of foundNode

NodeWrapper wrapper = new NodeWrapper();
findGivenNode(root, wrapper, key, parentStack);

Then inside your function instead of:

foundNode = node;

You say:

wrapper.foundNode = node;

This way you can maintain the reference throughout the recursion inside the NodeWrapper. Meaning:

NodeWrapper wrapper = new NodeWrapper();
findGivenNode(root, wrapper, key, parentStack);
// at this point, wrapper.foundNode will hold the reference to the node you need
// or null if the node wasn't found

On another note, above the method you have this function prototype:

findGivenNode(root, key, foundNode, parentStack);

Seems like someone is still used to C/C++ :)

This is unnecessary in Java, you can read this question thread for reasoning behind that or just Google it.

thanks for the clarification, but by setting (foundNode = node) I am trying to get the reference of the node that has the key and not the node itself. Secondly, foundNode is just a reference variable so can't set the value by calling any of the setter methods. — Meena Chaudhary, Sep 19 '14 at 06:22
To the secondly part, Yes it can. `foundNode` points to the node you want to change so it has access to the methods of that node. — nem035, Sep 19 '14 at 06:43
But changing the node is not the point of setting the reference variable to that node. All I need is a reference to that node. which I am not getting unless I do something like `foundNode = node; return foundNode;` And change the method's return type from `void` to `Node`. — Meena Chaudhary, Sep 19 '14 at 07:07

Unable to set reference variable in recursive call

1 Answers1