n-ary Tree structure: implementation and children insertion to a node

Hello and good day :)

Today I will be dealing with an interesting topic to me. N-ary trees. What I usually find on the web is related to binary trees and I was interested in n-ary tree for my own side project and decided to make my own implementation of it. If you don't like it or would like to tweak it just scream and shout in the comment section bellow and I will do something about it, maybe ;)


First of all, let us start with the set up for a tree structure.

public class GrocerieTree 
{
   public GrocerieTreeNode Root;

   public GrocerieTree()
   {
   } 
}

public class GrocerieTreeNode
{
   int Id;
   String Data;
   GrocerieTreeNode Parent;
   ArrayList<GrocerieTreeNode> Children;
  
   public GrocerieTreeNode(int id, String data)
   {
      Id = id;
      Data = data;
   }
}

Ok, so here is the basic tree structure. Tried to keep it as simple as I can, you can complicate the structure by expanding the data of the node class. Inside, a class for the tree node is defined. It has the parent reference, the list of children, id and the data which is represented with a string. We will need the Id because it will be key we will use for traversing through the tree.

Now that the basic structure has been defined we will go straight into adding the nodes. The difference is that here I want to add a list of nodes to an existing node. Reason for that is efficiency, if we traverse through the tree every time we need to only one node, why don't we add a list of nodes instead, it requires less searches in the tree, less computations and it is a lot faster :).

public int AddChildrenNodes(GrocerieTreeNode rootNode, int parentId, ArrayList<GrocerieTreeNode> nodesToAdd)
{
   if(rootNode == null)
   {
      return 0;
   }
  
   if(rootNode.Children==null)
   {
      rootNode.Children = new ArrayList<GrocerieTreeNode>();
   }
  
   if(rootNode.Id == parentId)
   {
      for(int i=0; i< nodesToAdd.size(); i++)
      {
         GrocerieTreeNode nd = nodesToAdd.get(i);
         nd.Parent = rootNode;
         rootNode.Children.add(nd);
      }  
      return 1;
   }
   else
   {
      for(int i=0; i < rootNode.Children.size(); i++)
      {
         int resultFlag = AddChildrenNodes(rootNode.Children.get(i), parentId, nodesToAdd);
         if(resultFlag == 1)
         {
            return 1;
         } 
      }
   }  
   return -1;
}

All in all, this method is quite simple. If we found the node that has the required Id add the children to the node. Remember, we are not dealing with binary tree here and there is no, go left then go right. You have to find the parent node, do calculations with an array of children and return the result. I have used an integer return here, which is maybe too much, but you will never know :).

• -1 means that id wasn't found in the current node.
• 1 means that input was successful
• 0 means that we came to the leaf of the tree or that root node was null from the start

Also notice the recursion in this method. The mechanism is: we come to a node and if it is not the one we are looking for, we check the children of the node, and then children of the children and etc. The direction of the traversing is always go left until you come to an end and then go right. If you want to switch the direction pay closer attention to the for loop in the else part of the method. Depending on your array data sorting and the direction of the for loop itself (ascending, descending or any way you like) you can control the tree traversing direction.

One last thing about the method, the adding of the parent node to the child in the if(rootNode.Id == parentId) block. I have decided intentionally to add the parent node at this point because the array of nodes will probably be defined outside the tree. The only thing you need is the parentId which is the id of the node we are attaching children to be able to add them to that node. If we looked for the parent node outside of the tree, to me it wouldn't be that efficient. While we are traversing through the tree, why not use the currently inspected and found node to be the parent :). Also, to be mentioned, the adding of the parent is not completely necessary. If you just need the node data, and not the parent data in the display/usage of the current node, you can replace the for loop for adding the children nodes with  rootNode.Children.addAll(nodesToAdd) which is a bit more efficient, because you are not traversing through the Children node list.

Here is an animated gif I made that describes the process of insertion visually. Don't judge me by my animation and drawing foo, I gave my best :).

• Blue square represent the current node while traversing for the tree
• Red square represents that the node of interest was found and insertion of the children can be performed.

I will end today's ramblings with an example for adding the nodes to the tree.

Root = new GrocerieTreeNode(0, "Root");
int parentId = Root.Id;

GrocerieTreeNode newNodeBread = new GrocerieTreeNode(1, "Bread");
GrocerieTreeNode newNodeMilk = new GrocerieTreeNode(2, "Milk");
GrocerieTreeNode newNodeMeat = new GrocerieTreeNode(3, "Meat");
GrocerieTreeNode newNodeEggs = new GrocerieTreeNode(4, "Eggs");
ArrayList<GrocerieTreeNode> nodeList = new ArrayList<GrocerieTreeNode>();
nodeList.add(newNodeBread);
nodeList.add(newNodeMilk);
nodeList.add(newNodeMeat);
nodeList.add(newNodeEggs);  
AddChildrenNodes(Root, parentId, nodeList);
  
parentId = newNodeBread.Id;

GrocerieTreeNode newNodeBreadW = new GrocerieTreeNode(20, "White Bread");
GrocerieTreeNode newNodeBreadC = new GrocerieTreeNode(21, "Corn Bread");
GrocerieTreeNode newNodeBreadWG = new GrocerieTreeNode(22, "Whole Grain Bread");
GrocerieTreeNode newNodeBreadWT = new GrocerieTreeNode(23, "White Toast Bread");
GrocerieTreeNode newNodeBreadWGTB = new GrocerieTreeNode(24, "Whole Grain Toast Bread");

ArrayList<GrocerieTreeNode> nodeList2 = new ArrayList<GrocerieTreeNode>(); 
nodeList2.add(newNodeBreadW);
nodeList2.add(newNodeBreadC);
nodeList2.add(newNodeBreadWG);
nodeList2.add(newNodeBreadWT);
nodeList2.add(newNodeBreadWGTB);
AddChildrenNodes(Root, parentId, nodeList2);

We have the Root node defined. "Bread, Milk, Meat, Eggs" are attached to the Root. Subcategories of the Bread "White Bread, Corn Bread, Whole Grain Bread" are attached as children to the "Bread" node.

Another long post from me today,
Hope this post was useful to someone as it was to me,
Have a nice day, Until next time