Introduction to N-ary Tree - The Coding Shala

Last Updated: 26-Jan-2021
Home >> Data Structures >> Introduction to N-ary Tree

 In this post, we will learn what is N-ary Tree and how to traverse the N-ary Tree using Preorder and Postorder.

Introduction to N-ary Tree

An N-ary tree is a rooted tree in which each node has no more than N children, called an N-ary tree also known as the k-way tree. So we can say that a binary tree is a special form of N-ary tree having N equals to 2. A Binary tree has no more than 2 children at each node.

Here is an example of 3-ary tree:


   A
       /    |   \
      B   C  D
     /  \   |
    E  F G

Trie is one of the most frequently used N-ary trees.

Traversal of N-ary Tree

Like a binary tree, we can also use the pre-order, post-order, and level-order traversal method to traversal an N-ary tree. 

Note: There is no standard definition for in-order traversal in n-ary trees.

Preorder Traversal of N-ary Tree

In an N-ary tree, preorder means visit the root node first and then traverse the subtree rooted at its children one by one.

Here is an example of Preorder Traversal of N-ary tree:

    A
       /   |  \
      B  C  D
     / \   |
   E  F G
   PreOrder: A-B-C-E-F-D-G

PostOrder Traversal of N-ary Tree

In an N-ary tree, postorder means traverse the subtree at its children first and then visit the root node itself.

Here is an example of postorder traversal of N-ary tree:

    A
       /   |  \
      B  C  D
      / \   |
    E  F G
PostOrder: B-E-F-C-G-D-A

Level-Order Traversal of N-ary Tree

In level-order traversal, we do a breadth-first search in a tree. We visit all the nodes at the same level first then we go to the next level.

Here is an example of level-order Traversal of N-ary tree:

    A
       /   |  \
      B  C  D
      / \   |
    E  F G
level-order: A-B-C-D-E-F-G


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Single Number 3 LeetCode Solution - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Java Method Overloading - The Coding Shala