Using recursively returned reference to node in tree does not allow changes to the node itself

Question

My data structures class is working with trees. We are implementing a 3-ary tree, containing 2 values with a reference to a left, middle, and right node (left subtree is less than value 1, middle subtree is between value 1 and value 2, right subtree is greater than value 2). An interface has been provided for the Tree class, and the find, insert, and delete methods must be recursive. The client code which this will be tested against uses the insert method repeatedly to create the tree, and the root starts off as null.

I'm trying to insert values into the tree recursively by finding the parent node in a separate private method, then changing the returned node as appropriate. The problem currently is that the method returns the initial node, which is the root, and correctly creates a new node with the value because the root is null. However, the root remains null.

I'm pretty certain this is due to the way that references and values work in Java (similar to C# as described in this article by Jon Skeet); given the constraints, how should I change this to allow insertions into the tree? Below is the current insert method in the tree class, along with the similar private method.

public void insert(AnyType newData)
{
 // If insert node is null, make a new node with newData as first key
 TernaryNode<AnyType> insert_node = findNode(newData, root);
 if (insert_node == null)
 {
  insert_node = new TernaryNode<AnyType>(newData);
 }
 else
 {
  // Get the key that is equal if the insert node is not null
     if (insert_node.getKey1() == null)
        {
            insert_node.setKey1(newData);
        }
        else
        {
         insert_node.setKey2(newData);
        }
 }// end else
}// end insert

private TernaryNode<AnyType> findNode(AnyType item, TernaryNode<AnyType> node)
{
 TernaryNode<AnyType> current_node = node;
 if (current_node != null)
 {
  if (current_node.getKey1() != item &&
    current_node.getKey2() != item)
  {
   // Comparator checks left
   if (compare.compare(current_node.getKey1(), item) <= -1)
   {
    return findNode(item, current_node.left);
   } // Comparator checks right
   else  if (compare.compare(current_node.getKey2(), item) >= 1)
   {
    return findNode(item, current_node.right);
   }// Comparator checks middle
   else
   {
    return findNode(item, current_node.middle);
   }
  }// end while
 }// end if
 // Return current node even if it is null
 return current_node;
}// end findNode

Answer 1

Unless you're assigning something to the root member, it will never acquire a value. You probably need some sort of outer container for your tree, similarly to how an XML document (which is also a tree) has an outer Document object which is distinct from the actual document root node.

Answer 2

    TernaryNode<AnyType> insert_node = findNode(newData, root);
    if (insert_node == null)
    {
            insert_node = new TernaryNode<AnyType>(newData);
            root = insert_node;
    }