equivalent of pass-by-reference in Java for null passed pointers

Question

I have a question about the best way of passing an object that might contain null to other methods. The other method will create a new instance if the object if the passed object is null. My question is on how to allow the second method to modify the origina initial passed null object pointer. Basically, I faced this problem while reading a BST from file and making the tree. I think explaining the problem using the same example makes more sens:

In the below code, I am reading and building a BST from all the values stored in a Queue. The Queue values are the In-Order traversal of the tree that I have read from another method.

    TreeNode root2;
public void readBST(Queue<Integer> input){
    if (input==null || input.isEmpty()) return;     
    int i=input.poll();
    root2 = new TreeNode(i);
    readBSTHelper(root2.leftChild , input, Integer.MIN_VALUE , i-1);
    readBSTHelper(root2.rightChild, input, i+1, Integer.MAX_VALUE);
}

private void readBSTHelper(TreeNode curr, Queue<Integer> input, int min, int max){
    if (input==null && input.isEmpty()) return;
    int i = input.peek();
    if (i>=min && i<=max){
        input.poll();
        curr = new TreeNode(i);
        readBSTHelper(curr.leftChild, input, min, i-1);
        readBSTHelper(curr.rightChild,input, i+1, max);
    }
}

However, the problem I am facing is that when the root2 is created, it's leftChild and rightChild are null. in fact TreeNode(i) makes a TreeNode with data=i and leftChild and rightChild equal null. When I call the readBSTHelper passing the root2.leftChild, it passes a null pointer. Since it is a null pointer a copy of the null pointer is passed to readBSTHelper. Thus, the result from the readBSTHelper is lost and never returned/assigned to the real root2.leftChild. We can prevent such a problem in C++ by passing the reference of the original pointer. I was able to temporarily solve the problem by modifying the code as below:

    TreeNode root2;
public void readBST(Queue<Integer> input){
    if (input==null || input.isEmpty()) return;     
    int i=input.poll();
    root2 = new TreeNode(i);
    readBSTHelper(root2, "left", input, Integer.MIN_VALUE , i-1);
    readBSTHelper(root2, "right", input, i+1, Integer.MAX_VALUE);
}
private void readBSTHelper(TreeNode curr, String side, Queue<Integer> input, int min, int max){
    if (input.isEmpty()) return;
    int i = input.peek();
    if (i>=min && i<=max){
        input.poll();
        if (side.equals("left")) {
            curr.leftChild = new TreeNode(i);
            readBSTHelper(curr.leftChild,"left", input, min, i-1);
            readBSTHelper(curr.leftChild, "right", input, i+1, max);
        } else {
            curr.rightChild = new TreeNode(i);
            readBSTHelper(curr.rightChild,"left", input, min, i-1);
            readBSTHelper(curr.rightChild, "right", input, i+1, max);
        }

    }
}

But this code looks ugly to me. Any advise on how to make the first code work?

You **can't** pass by reference in Java (well, _technically_ you can but it's a long and bothersome process with reflection). — Benjamin Gruenbaum, Mar 08 '13 at 07:09
Possible answer: http://stackoverflow.com/questions/15203969/java-access-variables-in-arguments/15204059#15204059 — Dariusz, Mar 08 '13 at 07:13
@Benjamin I know you can't pass by reference in java. My question was on how we can reach the equivalent functionality in the above code — reza, Mar 08 '13 at 07:20
possible duplicate of [Passing by reference in Java?](http://stackoverflow.com/questions/2504523/passing-by-reference-in-java) — jachguate, Mar 08 '13 at 07:20
@Dariusz I checked your suggestion but it is just a wrapper class. I can't see how a wrapper can solve the above problem. we are still calling the helper method with the null object that leads to the same problem. — reza, Mar 08 '13 at 07:21
@reza Initialize the nodes if null in the outer function and then do all the logic in the function itself — Benjamin Gruenbaum, Mar 08 '13 at 07:22
@jachguate This has NOTHING to do with Pass-by-reference. I mentioned that on the side. The question is how I can solve the problem of null pointer being copied in the sub-methods — reza, Mar 08 '13 at 07:23
@reza It looks like you have a problem that you can't solve with java with your current approach, and IMHO the suggested duplicate clearly answers your question. — jachguate, Mar 08 '13 at 07:27

Bernhard Barker · Accepted Answer · 2013-03-08T07:33:50.870

Option 1: Wrapper

class NodeWrapper
{
  TreeNode node;
}

class TreeNode
{
  ...
  TreeNode(int num)
  {
    leftChild = new NodeWrapper();
    rightChild = new NodeWrapper();
    ...
  }
  NodeWrapper leftChild, rightChild;
}

void readBSTHelper(NodeWrapper curr, Queue<Integer> input, int min, int max)
{
  ...
}

Option 2: Initialize children in constructor

I suggest having a separate constructor dedicated to this purpose (not as below), otherwise your insert function will create children in error.

class TreeNode
{
  ...
  TreeNode()
  {
    val = null;
  }
  TreeNode(int num)
  {
    init(num);
  }
  init(int num)
  {
    leftChild = new TreeNode();
    rightChild = new TreeNode();
    val == num;
  }
  Integer val;
}

public void readBST(Queue<Integer> input){
    if (input==null || input.isEmpty()) return;     
    int i=input.poll();
    root2 = new TreeNode(i);
    if (!readBSTHelper(root2.leftChild , input, Integer.MIN_VALUE , i-1))
      root2.leftChild = null; // delete child if not populated
    if (!readBSTHelper(root2.rightChild, input, i+1, Integer.MAX_VALUE))
      root2.rightChild = null; // delete child if not populated
}

boolean readBSTHelper(TreeNode curr, Queue<Integer> input, int min, int max){
    if (input==null && input.isEmpty()) return false;
    int i = input.peek();
    if (i>=min && i<=max){
        input.poll();
        curr.init(i);
        if (!readBSTHelper(curr.leftChild, input, min, i-1))
          curr.leftChild = null;
        if (!readBSTHelper(curr.rightChild, input, i+1, max))
          curr.rightChild = null;
        return true;
    }
    return false;
}

this looks like using a dummy node (here you called it NodeWrapper) for all the null TreeNodes. not bad but I am trying to see if I can use some other method to solve this. — reza, Mar 08 '13 at 07:26
@reza Actually `NodeWrapper` is for **all** `TreeNode`s, not just those that are `null`. Its purpose would be similar to a pointer in C++. Also added another option, see edit. — Bernhard Barker, Mar 08 '13 at 07:40
thanks for the second suggestion. But it also stores so many additional null values. It sets all the null children equal to a new TreeNode with null value. I am curious if this can also be prevented? — reza, Mar 08 '13 at 07:41
@reza Note that it removes them as it iterates back up the tree. Can't think of a better way right now. — Bernhard Barker, Mar 08 '13 at 07:43

equivalent of pass-by-reference in Java for null passed pointers

1 Answers1