Java object cannot passed by ref through recursion

Question

The problem is I need to write a function to validate whether a binary tree is a valid binary search tree

This is my code:

public static boolean betterValidBSTArray(TreeNode node) {
    WrapInt lastData = null;
    return validate(lastData, node);
}

private static boolean validate(WrapInt lastData, TreeNode node) {
    if(node == null) return true;
    if(!validate(lastData, node.getLeft())) return false;
    if(lastData != null && node.getData() <= lastData.value) return false;
    if(lastData == null) lastData = new WrapInt();
    lastData.value = node.getData();
    if(!validate(lastData, node.getRight())) return false;

    return true;
}

class WrapInt { int value; }

The problem is, this algorithm is not working. I put some break points and figure out that for each stack call, after lastData gets assigned to a value after the stack call finishes, the previous stack call will continue with lastData = null, even lastData has real value for the previous stack call.

Thank you for any help.

Override clone for your 'WrapInt' class, and then try passing a clone of 'lastData' object each time you call your validate method recursively. — STaefi, Jul 21 '15 at 06:14

score 2 · Answer 1 · answered Jul 21 '15 at 07:45

To fix your code you should not do if(lastData == null) lastData = new WrapInt(); as it assigns the reference to the new object only into the method call parameter which is local variable for each stack call, and you should pass not null as lastData but an object which will be used across the whole recursion, changing only its value.

score 2 · Answer 2 · edited May 23 '17 at 12:30

You're making a wrong assumption in the way references work.

public static boolean betterValidBSTArray(TreeNode node) { WrapInt lastData = null; return validate(lastData, node); }

You seem to think this will pass the address of lastData down to validate, and set it with an object when the right condition is triggered.

But what this really does is:

   return validate(null, node);

because the value of lastData = null.

You must pass down the object you want filled by underlying method because references are always passed by value. (so you pass the value null down, not the address of the lastData variable like you would if you did &lastData in c++).

for a better explanation see the answers here

the solution would be to create the reference outside, then pass it down into your method to use.

public static boolean betterValidBSTArray(TreeNode node) {
     WrapInt lastData = new WrapInt();
     return validate(lastData, node);
}

if you want to have to distinction between null/not null (if this holds a meaning in your code, for instance having found it) you can either use

class WrapInt {
    Integer value;
}

or

class WrapInt {
    private int value;
    private boolean set;
    public boolean wasSet() { return set; }
    public int getValue() { return value; } 
    public void setValue(int value) { this.value = value; set = true; }
}

So that the code outside the recursion has access to this state information.

score 0 · Answer 3 · answered Jul 21 '15 at 06:32

0

You need to create the WrapInt() object in the betterValidBSTArray and assign null to its value. This way you are passing the lastData reference around. Try this and it will work.

answered Jul 21 '15 at 06:32

Michael P

2,017
3
25
33

Assign `null` to a primitive? – Fildor Jul 21 '15 at 06:50

Java object cannot passed by ref through recursion

3 Answers3