N-Ary Trees

What is N-ary tree?

An n-ary tree is a tree data structure where each node can have at most n children. Unlike binary trees, which have at most two children per node, n-ary trees allow for a variable number of children. They are used in scenarios where each node may have multiple possible paths or branches, such as in hierarchical data structures or decision trees.

Types of N-ary Tree

Here is a list of some types of N-ary trees:

1. Full N-ary Tree
    
2. Complete N-ary Tree
    
3. Perfect N-ary Tree
    
4. Balanced N-ary Tree
    
5. M-ary Tree
    
6. B-Tree
    
7. Trie (Prefix Tree)
    
8. K-ary Tree

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;
  List<NAryTree> children = new LinkedList<>();

  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  

To learn more about these traversal techniques, click here Tree Traversal Techniques to read a fantastic article about the same.

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

• java

java

import java.util.List;
import java.util.LinkedList;
import java.util.Queue;

public class NArTree {
  public static class NAryTree{
      int data;
      List<NAryTree> children = new LinkedList<>();

      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<NAryTree> queue = new LinkedList<>();
      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);
  }
}

You can also try this code with Online Java Compiler

Run Code

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

Frequently Asked Questions

What is a 5 ary tree?

A "5-ary tree" is an N-ary tree in which each node can have up to five children. It's a specific type of N-ary tree where each node can have a maximum of five descendants or sub-trees.

Is every binary search tree an N-ary tree?

No, not every binary search tree (BST) is an N-ary tree. A binary search tree is a specific type of binary tree where each node has at most two children, and it follows a specific ordering property where values in the left subtree are smaller and values in the right subtree are larger than the node's value. N-ary trees, on the other hand, can have more than two children per node, making them more flexible in terms of branching.

What are the three types of binary tree?

Three common types of binary trees include the Full Binary Tree, where nodes have either 0 or 2 children; the Complete Binary Tree, where all levels are filled, possibly except the last, filled from left to right; and the Balanced Binary Tree, where the height difference of left and right subtrees is at most one, ensuring efficient operations.

What is the difference between a binary tree and an m-ary tree?

A binary tree restricts nodes to have at most two children (left and right), while an m-ary tree permits nodes to have up to m children, where m is any positive integer greater than or equal to 2, offering greater flexibility in representing hierarchical structures.

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

• Encode N-Ary Tree to Binary Tree
• N-Ary Tree Level Order Traversal
• Zig Zag Tree Traversal 
• Preorder Traversal

You can also consider our Online Coding Courses such as the DSA in Python, C++ DSA Course, DSA in Java Course to give your career an edge over others.

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  Coding Ninjas Studio.