C# Node pointer issue

Question

I am having some trouble setting child nodes using C#. I am trying to build a tree of nodes where each node holds an int value and can have up to a number of children equal to it's value.

My issue appears when I iterate in a node looking for empty(null) children so that I may add a new node into that spot. I can find and return the null node, but when I set the new node to it, it loses connection to the parent node.

So if I add 1 node, then it is linked to my head node, but if I try to add a second it does not become a child of the head node. I am trying to build this with unit tests so here is the test code showing that indeed the head does not show the new node as it's child (also confirmed with visual studios debugger):

  [TestMethod]
  public void addSecondNodeAsFirstChildToHead()
  {
     //arange
     Problem3 p3 = new Problem3();
     p3.addNode(2, p3._head);
     Node expected = null;
     Node expected2 = p3._head.children[0];
     int count = 2;

     //act
     Node actual = p3.addNode(1, p3._head);
     Node expected3 = p3._head.children[0];

     //assert
     Assert.AreNotEqual(expected, actual, "Node not added"); //pass
     Assert.AreNotEqual(expected2, actual, "Node not added as first child"); //pass
     Assert.AreEqual(expected3, actual, "Node not added as first child"); //FAILS HERE
     Assert.AreEqual(count, p3.nodeCount, "Not added"); //pass
  }

Here is my code.

public class Node
   {
      public Node[] children;
      public int data;

      public Node(int value)
      {
         data = value;
         children = new Node[value];

         for(int i = 0; i < value; i++)
         {
            children[i] = null;
         }
      }
   }

   public class Problem3
   {
      public Node _head;
      public int nodeCount;

      public Problem3()
      {
         _head = null;
         nodeCount = 0;
      }

      public Node addNode(int value, Node currentNode)
      {
         if(value < 1)
         {
            return null;
         }

         Node temp = new Node(value);

         //check head
         if (_head == null)
         {
            _head = temp;
            nodeCount++;
            return _head;
         }

         //start at Current Node
         if (currentNode == null)
         {
            currentNode = temp;
            nodeCount++;
            return currentNode;
         }

         //find first empty child
         Node emptyChild = findEmptyChild(currentNode);
         emptyChild = temp;
         nodeCount++;
         return emptyChild;
      }

      public Node findEmptyChild(Node currentNode)
      {
         Node emptyChild = null;
         //find first empty child of current node
         for (int i = 0; i < currentNode.children.Length; i++)
         {
            if (currentNode.children[i] == null)
            {
               return currentNode.children[i];
            }
         }
         //move to first child and check it's children for an empty
         //**this causes values to always accumulate on left side of the tree
         emptyChild = findEmptyChild(currentNode.children[0]);
         return emptyChild;
      }

I feel the problem is I am trying to treat the nodes as pointers like I would in C++ but that it is not working as I expect.

Answer 1

Look at this part of your code:

Node temp = new Node(value);
//...
Node emptyChild = findEmptyChild(currentNode);
emptyChild = temp;

You are assigning the emptyChild to a new node, doing so you will "loose" the connection with any parent node. You should write something like this:

emptyChild.data = temp.data;
emptyChild.children = temp.children;

As others said, your approach using null checking could be improved. You mentioned that Node.data holds the numbers of children of a given node, so you could simply say that when you have Node.data == 0, that node should be treated as being null, or empty. For example, instead of having:

rootNode.children[0] = null; // rootNode can have a lot of children
rootNode.children[1] = null;
//...

you would have:

rootNode.children[0] = new Node(0);
rootNode.children[1] = new Node(0);
//...

At this point your code will look similar to this:

public class Node
{
    public Node[] children;
    public int data;

    public Node(int value)
    {
        data = value;
        children = new Node[value];

        // Instead of "pointing" to null,
        // create a new empty node for each child.
        for (int i = 0; i < value; i++)
        {
            children[i] = new Node(0);
        }
    }
}

public class Problem3
{
    public Node _head;
    public int nodeCount;

    public Problem3()
    {
        _head = null;
        nodeCount = 0;
    }

    public Node addNode(int value, Node currentNode)
    {
        if (value < 1)
        {
            return null;
        }

        Node temp = new Node(value);

        //check head
        if (_head == null)
        {
            _head = temp;
            nodeCount++;
            return _head;
        }

        //start at Current Node
        if (currentNode == null)
        {
            currentNode = temp;
            nodeCount++;
            return currentNode;
        }

        //find first empty child
        Node emptyChild = findEmptyChild(currentNode);
        if (emptyChild != null)
        {
            emptyChild.data = temp.data;
            emptyChild.children = temp.children;
            nodeCount++;
        }
        return emptyChild;
    }

    public Node findEmptyChild(Node currentNode)
    {
        // Null checking.
        if (currentNode == null)
            return null;

        // If current node is empty, return it.
        if (currentNode.data == 0)
            return currentNode;

        // If current node is non-empty, check its children.
        // If no child is empty, null will be returned.
        // You could change this method to check even the
        // children of the children and so on...
        return currentNode.children.FirstOrDefault(node => node.data == 0);
    }
}

Let's look now at the testing part (please see the comments for clarification):

[TestMethod]
public void addSecondNodeAsFirstChildToHead()
{
    //arange
    Problem3 p3 = new Problem3();
    p3.addNode(2, p3._head); // Adding two empty nodes to _head, this means that now _head can
                             // contain two nodes, but for now they are empty (think of them as
                             // being "null", even if it's not true)
    Node expected = null;
    Node expected2 = p3._head.children[0]; // Should be the first of the empty nodes added before.
                                           // Be careful: if you later change p3._head.children[0]
                                           // values, expected2 will change too, because they are
                                           // now pointing to the same object in memory
    int count = 2;

    //act
    Node actual = p3.addNode(1, p3._head); // Now we add a non-empty node to _head, this means
                                           // that we will have a total of two non-empty nodes:
                                           // this one fresly added and _head (added before)
    Node expected3 = p3._head.children[0]; // This was an empty node, but now should be non-empty
                                           // because of the statement above. Now expected2 should
                                           // be non-empty too.

    //assert
    Assert.AreNotEqual(expected, actual, "Node not added"); //pass

    // This assert won't work anymore, because expected2, expected 3 and actual 
    // are now pointing at the same object in memory: p3._head.children[0].
    // In your code, this assert was working because 
    // In order to make it work, you should replace this statement:
    //    Node expected2 = p3._head.children[0];
    // with this one:
    //    Node expected2 = new Node(0); // Create an empty node.
    //    expected2.data = p3._head.children[0].data; // Copy data
    //    expected2.children = p3._head.children[0].children;
    // This will make a copy of the node instead of changing its reference.
    Assert.AreNotEqual(expected2, actual, "Node not added as first child");

    // Now this will work.
    Assert.AreEqual(expected3, actual, "Node not added as first child");
    Assert.AreEqual(count, p3.nodeCount, "Not added"); //pass
}

Answer 2

It is impossible for a function to return a handle (or a pointer) to something that does not yet exist. Either you initialize non existent value inside the function, or you provide enough variables for it to be initialized outside of the function.

One solution would be to rename the function findEmptyChild to something like initializeEmptyChild(Node currentNode, Node newNode), adding one more Node parameter to it (when calling it that would be temp value), and in the loop before return you initialize the previously empty Node, currentNode.children[i] = newNode.

Another solution would be not to return just one Node but two values, a parent node and an index where empty child is found, Tuple<Node, int> findEmptyChild(Node currentNode), and in the loop instead of return currentNode.children[i] you do return new Tuple<Node, int>(currentNode, i). When calling the function you would change the code to

var parentAndIndex = findEmptyChild(currentNode);
parentAndIndex.Item1.children[parentAndIndex.Item2] = temp;