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?

Answer 1

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