 New update is available. Click here to update.

# N-Ary Trees

## Introduction

The N-ary tree data structure is a complex binary tree data structure that allows us to have multiple children at each node, similar to the binary tree data structure, but with n number of children. This structure is slightly more complex than the prevalent binary trees. The only difference between an N-ary and a binary tree is in their shapes. In an N-ary, we can add and remove leaves (and therefore branches) from the root of the system during its construction.

A famous example of an N-ary tree would be London’s famous London Eye Ferris wheel.

N-ary Trees hold certain advantages over Binary Trees, namely that it takes up significantly less space when there is no more room to grow vertically in a Binary Tree. This also allows for linear storage of data rather than the tree-like structure used in Binary Trees, making it perfect for database files where you would like to save as much space as possible without sacrificing too much speed or efficiency.

## General Idea

N-ary trees are a variety of binary trees. They differ by having a single node at the top which holds multiple children. These children may have their children, themselves being n-ary trees with one "level" of depth less than their parents. Thus, at any level, the maximum number of children a node can have is n.

### Example and Explanation

Let us consider the following graph. In the example, we can see that there is one root node with some children. Here we have decided to keep our n value as 3. So, the number of children each node has is less than or equal to 3. This tree can also be called a 3-Ary tree.

## N-Ary Tree Approach

Since trees are not native data types for any programming language, we use constructors to make our tree. The language of our choice is Java, as we will be using the List, Linked List, and Queue functions under the util package.

Our constructor will look like this:

``````public static class NAryTree{
int data;

NAryTree(int data){
this.data = data;
}

NAryTree(int data,List<NAryTree> child){
this.data = data;
children = child;
}
}``````

Here we have used the util package functions- List and LinkedList to create our tree data structure.

To print our tree, we have four ways. They are:

• Inorder Traversal
• Preorder Traversal
• Postorder Traversal
• Level Order Traversal

For printing our tree, we take the help of Queue. We add the child nodes one by one and then print them level-wise.

### Java implementation

``````import java.util.List;
import java.util.Queue;

public class NArTree {
public static class NAryTree{
int data;

NAryTree(int data){
this.data = data;
}

NAryTree(int data,List<NAryTree> child){
this.data = data;
children = child;
}
}

private static void printNAryTree(NAryTree root){
if(root == null) return;
queue.offer(root);
while(!queue.isEmpty()) {
int len = queue.size();
for(int i=0;i<len;i++) {
NAryTree node = queue.poll();
assert node != null;
System.out.print(node.data + " ");
for (NAryTree item : node.children) {
queue.offer(item);
}
}
System.out.println();
}
}

public static void main(String[] args) {
NAryTree root = new NAryTree(10);   //root; level 0

root.children.add(new NAryTree(20));    //1st child node of root
root.children.add(new NAryTree(30));    //2nd child node of root
root.children.add(new NAryTree(40));    //3rd child node of root

root.children.get(0).children.add(new NAryTree(50));    //1st child of 1st child node
root.children.get(0).children.add(new NAryTree(60));    //2nd child of 1st child node
root.children.get(0).children.add(new NAryTree(70));    //3rd child of 1st child node

root.children.get(1).children.add(new NAryTree(80));    //1st child of 2nd child node
root.children.get(1).children.add(new NAryTree(90));    //2nd child of 2nd child node
root.children.get(1).children.add(new NAryTree(100));   //3rd child of 2nd child node

root.children.get(2).children.add(new NAryTree(110));   //1st child of 3rd child node

printNAryTree(root);
}
}``````

Output

``````10
20 30 40
50 60 70 80 90 100 110 ``````

### Complexity Analysis

Time Complexity

In the given implementation, while insertion, we visit each node exactly once, thus the time complexity is,T(n) = O(N), where N is the number of nodes.

Space Complexity

In the given implementation, we are just storing the tree. Thus, Space Complexity = O(N), where N is the size of the tree.

Check out this problem - Mirror A Binary Tree

### What is an n-ary tree in data structure?

Each node in a generic or n-ary tree is a data structure made up of records and a list of pointers to its children (duplicate references are not allowed). Each node maintains the addresses of numerous other nodes, unlike the linked list where each node holds the reference of only its neighbors at max.

### How are n-ary trees implemented?

An n-ary tree can be implemented using a struct in C++ or a custom user-defined class in Java. Each node of an n-ary tree is a data structure in itself that holds its children in a list. We can create a class NAryNode in Java to represent a node of an n-ary tree. In this class, there should be a list data member to hold the children and a method to populate the list.

### Is an n-ary tree a graph?

Yes, an n-ary tree has all properties required to be called a graph. It can be considered a rooted tree where the number of children of each node can be more than two. The number of children of each node in an n-ary tree can be up to n.

### What are the uses of N-Ary Trees Data Structure?

The N-Ary trees can be used to show a computer’s storage hierarchy. On top, there can be “This PC” as the root. Below it, there can be various drives like- C:, D:, E:, etc. Then the multiple folders, sub-folders, and files.

## Conclusion

To summarize this article, we learned about the N-Ary tree data structure. We saw its example, approach, and implementation. We also studied the time and space complexities and covered a few FAQs.

Recommended Problems

Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.

Learn various topics from Web Technologies, Programming Fundamentals, Data Structures, and Algorithms from our Library.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and Interview Experiences curated by top Industry Experts only on  CodeStudio.

Happy Coding! 