Nary Tree Data Structure
The Nary tree is a tree that allows us to have n
number of children of a particular node, hence the name Nary, making it slightly complex than the very common binary trees that allow us to have at most 2 children of a particular node.
A pictorial representation of an Nary tree is shown below:
In the Nary tree shown above, we can notice that there are 11 nodes in total and some nodes have three children and some have had one only. In the case of a binary tree, it was easier to store these children nodes as we can assign two nodes (i.e. left and right) to a particular node to mark its children, but here it's not that simple. To store the children nodes of any tree node we make use of another data structure, mainly vector in C++ and LinkedList in Java.
Implementation of Nary Tree
The first thing that we do when we are dealing with nonlinear data structures is to create our own structure (constructors in Java) for them. Like in the case of a binary tree, we make use of a class TreeNode
and inside that class, we create our constructors and have our classlevel variables.
Consider the code snippet below:
public static class TreeNode{
int val;
List<TreeNode> children = new LinkedList<>();
TreeNode(int data){
val = data;
}
TreeNode(int data,List<TreeNode> child){
val = data;
children = child;
}
}
In the above code snippet, we have a class named TreeNode
which in turn contains two constructors with the same name, but they are overloaded (same method names but with different parameters) in nature. We also have two identifiers, one of them is the val that stores the value of any particular node, and then we have a List to store the children nodes of any node of the tree.
The above snippet contains the basic structure of our tree, and now are only left with making one and then later we will see how to print the tree using level order traversal. To build a tree we will make use of the constructors that we have defined in the above classes.
Consider the code snippet below:
public static void main(String[] args) {
// creating an exact replica of the above pictorial Nary Tree
TreeNode root = new TreeNode(1);
root.children.add(new TreeNode(2));
root.children.add(new TreeNode(3));
root.children.add(new TreeNode(4));
root.children.get(0).children.add(new TreeNode(5));
root.children.get(0).children.add(new TreeNode(6));
root.children.get(0).children.add(new TreeNode(7));
root.children.get(1).children.add(new TreeNode(8));
root.children.get(2).children.add(new TreeNode(9));
root.children.get(2).children.add(new TreeNode(10));
root.children.get(2).children.add(new TreeNode(11));
printNAryTree(root);
}
First thing first, we created the root node of our Nary Tree, then we have to assign some children to this root node, we do this by making use of the dot(.
) operator and accessing the children property of the root node and then adding different children to the root nodes by using the add method provided by the List
interface. Once we have added all the children of the root node, it is time to add children of each of the new level nodes, we do that by first accessing that node by using the get method provided by the list interface and then adding the respective children nodes to that node.
Lastly, we print this Nary Tree, we did it by calling the printNAryTree
method.
Now, since printing a tree is not as simple as looping through a collection of items, we have different techniques (algorithms precisely) at our disposal. These are mainly:

Inorder Traversal

Preorder Traversal

PostOrder Traversal

Level Order Traversal
For the sake of this tutorial, we will use the Level Order Traversal approach, as it is easier to understand, provided if you have seen how it works on a binary tree before.
Level Order Traversal (Printing the Nary Tree)
The Level Order traversal of any tree takes into the fact that we want to print the nodes at a root level first, then move on to the next level and keep repeating this process until we are at the last level. We make use of the Queue data structure to store the nodes at a particular level.
Consider a simple Nary Tree shown below:
Level Order Traversal for the above tree will look like this:
1
2 3 4 5
Consider the code snippet below:
private static void printNAryTree(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int len = queue.size();
for(int i=0;i<len;i++) { // so that we can reach each level
TreeNode node = queue.poll();
System.out.print(node.val + " ");
for (TreeNode item : node.children) { // forEach loop to iterate over all childrens
queue.offer(item);
}
}
System.out.println();
}
}
The entire code looks something like this:
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class NAryTree {
public static class TreeNode{
int val;
List<TreeNode> children = new LinkedList<>();
TreeNode(int data){
val = data;
}
TreeNode(int data,List<TreeNode> child){
val = data;
children = child;
}
}
private static void printNAryTree(TreeNode root){
if(root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int len = queue.size();
for(int i=0;i<len;i++) {
TreeNode node = queue.poll();
assert node != null;
System.out.print(node.val + " ");
for (TreeNode item : node.children) {
queue.offer(item);
}
}
System.out.println();
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.children.add(new TreeNode(2));
root.children.add(new TreeNode(3));
root.children.add(new TreeNode(4));
root.children.get(0).children.add(new TreeNode(5));
root.children.get(0).children.add(new TreeNode(6));
root.children.get(0).children.add(new TreeNode(7));
root.children.get(1).children.add(new TreeNode(8));
root.children.get(2).children.add(new TreeNode(9));
root.children.get(2).children.add(new TreeNode(10));
root.children.get(2).children.add(new TreeNode(11));
printNAryTree(root);
}
}
The output of the above code is:
1
2 3 4
5 6 7 8 9 10 11
We can compare this output to the pictorial representation of the Nary tree we had in the starting, each level node contains the same values.
Types of Nary Tree
Following are the types of Nary tree:
1. Full Nary Tree
A Full Nary Tree is an Nary tree that allows each node to have either 0 or N children.
Consider the pictorial representation of a full Nary tree shown below:
Notice that all the nodes of the above Nary have either 4 children or 0, hence satisfying the property.
2. Complete Nary Tree
A complete Nary tree is an Nary tree in which the nodes at each level of the tree should be complete (should have exactly N children) except the last level nodes and if the last level nodes aren't complete, the nodes must be "as left as possible".
Consider the pictorial representation of a complete Nary tree shown below:
3. Perfect Nary Tree
A perfect Nary tree is a full Nary tree but the level of the leaf nodes must be the same.
Consider the pictorial representation of a perfect Nary tree shown below:
Conclusions
 We learned what an Nary tree is.
 We also learned how to implement an Nary tree in Java(via level order traversal).
 Then we learned what different types of Nary trees are there in total.