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;
    }
}

Answer 1

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:

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:

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.