Generic N-ary Tree Traversal

Traversal in a tree is a process of visiting each node of a tree. We can not randomly access any node. As every node in a tree is connected through edges, we need to start from the root node to traverse the node. There are many ways to traverse a generic tree ( N-ary tree) but we will be discussing 2 of the commonly used traversals :

1. Pre-Order traversal
2. Post-Order traversal

Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.

What is Pre-Order Traversal in a Generic Tree ?

Pre-Order Traversal method in generic trees means the first visit of every node in the euler path. We can also say that when we are on the left side of the node in the euler. 

Take this example

Starting from the Root 10 , and following the pre-order , we print 10 and then move towards the first child 20 print it, then the next child 30 and print it ,now  in 30 we first visit its first child 50 print it then move to 60 print it and now the last child of 10 i.e. 40 is visited and printed.

We print the nodes in the first visited i.e. when the euler is in the left.

For example, see this :

So, the output for the Pre-Order Traversal will be :

10 -> 20 -> 30 -> 50 -> 60 -> 40.

ALGORITHM :

preOrder( root )

1. Visit/Print the root
2. Recursively traverse all the child sub trees.

Let’s code preOrder function implementation in java :

public static void preOrder(Node node){
    // Preorder traversal
    if(node == null) return;
    System.out.println(node.data);
    for(Node child:node.children)
    {
        preOrder(child);
    }
  }

Now, Let’s move towards the post order traversal in a generic tree.

What is Post-Order Traversal in a Generic Tree ( N-ary Tree) ?

Pre-Order Traversal method in generic trees means the last visit of every node in the euler path.We can also say that when we are on the right side of the node in the euler. 

Take this example :

Starting from the Root 10 , and following the post-order traversal, we move towards the first child 20 and when exiting print it, then the next child 30,now in 30 we first visit its first child 50 and on exiting print it then move to 60 and on exiting print it and now print 30 while exiting it. Now we visit 40 and print it on exiting and at last print the root node 10.

We print the nodes in the last visit i.e. when the euler is on the right.

For example, see this :

So, the output for the Post-Order Traversal will be :

20 -> 50 -> 60 -> 30 -> 40 -> 10 .

ALGORITHM :

postOrder( root )

1. Recursively traverse the children.
2. Print the node.

Let’s code preOrder function implementation in java :

public static void postOrder(Node node){
    // Preorder traversal
    if(node == null) return;
    for(Node child:node.children)
    {
        postOrder(child);
    }
   System.out.println(node.data);
  }

Thanks for reading and learning from CodingBroz. Learn more about Generic Tree (N-ary Tree) from here.