Need help in n tree implementation

Question

I am trying to implement n-ary kind of data structure using c #. The tree will have a root node and array of children and each child in the children array will also have set of children node. What I am trying to do is whenever we add children array that should be added to all the child present in the leaf node. my code is

      public void addChildren(Node root, Node[] children)
        {

             if (root.children == null)
            {
                root.children = children;

            }
            else
            {
                for (int i = 0; i < root.children.Length; i++)
                {

                    addChildren(root.children[i], children);
                }
            }

        }

Main program

     Dictionary<String, String[]> measurelist = new Dictionary<string, string[]>();
        String[] values = { "y", "n" };
        measurelist.Add("m1", values);
        measurelist.Add("m2", values);
        measurelist.Add("m3", values);           
        foreach (KeyValuePair<String, String[]> entry in measurelist)
        {
            Node[] children = new Node[entry.Value.Length];
           for(int i = 0; i < entry.Value.Length ;i ++)
            {
                Node child = new Node(entry.Key+":"+entry.Value[i]);
                children[i] = child;
            }

            clustertree.addChildren(clustertree.root, children);               
        }

but this code results in infinite recursive calls. I tried but unable to figure out what is going wrong? Please help me to find out what I am doing wrong. I have described the problem in the image

Solution: With the help of you I have found the solution to this issue. If I explain the root cause I think it will be helpful for others who may face the same issue. The main cause of the issue when I am passing the children array of nodes it is passed as a reference not by values. I have changed my code a little in order to make sure that the same children array reference is not passed to the next recursion call.

Here is my corrected code:

 public void addChildren(Node root, Node[] children)
        {

             if (root.children == null)
            {

                root.children = children;

            }
            else
            {
                for (int i = 0; i < root.children.Length; i++)
                {                       
                    Node[] children1 = new Node[children.Length];
          //I am creating a new array and nodes and passing the newly created array to                                       the next recursive call
                    for (int j = 0; j < children.Length; j++)
                    {
                        Node node = new Node(children[j].key);                           
                        node.children = children[j].children;
                        children1[j] = node;
                    }
                    addChildren(root.children[i], children1);
                }
            }

        }

Thanks again :)

Answer 1

You are not creating the tree as you've shown in diagram, rather you're doing something like below:

       R
      / \
     /   \
    a1   a2 (children of this are actually b1 and b2)
   / \   
  /   \
 b1   b2

When you add the b1, b2 as children of a2 you're referencing to the same b1 and b2 that have been alreayd added to a1.

In next iteration when you add c1 and c2, according to your algorithm you reference c1 and c2 to both b1 and b2 firstly via a1 but your function does not stop here, it goes again to b1 and b2 this time via a2, but since c1 and c2 have been already added as children of b1 and b2, the algorithm gets confuse and goes into forever loop.

To solve this problem:

Find the last level of tree but till last level only use recursive path using one child only.

public boolean addChildren(Node root, Node[] children)
{

    if (root.children == null)
    {
        root.children = children;
        return true;
    }
    else
    {
        for (int i = 0; i < root.children.Length; i++)
        {
            /* if it returns true then it was last level 
                   else break */
            if(!addChildren(root.children[i], children)) 
            {
                /* this is non-last level break */
                break;
            }
        }
    }
    return false;
}

Answer 2

You should probably make your internal node[] into a list<node> instead of an array.

Then use this code

      public void addChildren(Node root, Node[] children)
        {

            if (root.children == null)
            {
                root.children = new List<Node>();

            }

            root.children.AddRange(children);

        }