Saturday, 26 September 2020

N-ary tree preorder traversal in java

N-ary tree preorder traversal in java

This is a popular interview question asked in Tier-1 companies.

Given an n-ary tree, print preorder traversal of its nodes values.

Example of N-ary tree preorder traversal below:

n-ary tree preorder traversal example

Algorithm

Preorder traversal: To traverse a Binary Tree in Preorder, following operations are carried-out 
  1. Visit the root node and print data of that node. 
  2. Traverse the left subtree, and 
  3. Traverse the right subtree.

Preorder traversal of N-ary tree is very similar to that of Binary tree preorder traversal, only difference is instead of two children in Binary tree here we have N children.

Preorder traversal of Binary tree: Binary Tree Preorder Traversal

Considering the example above, 
we will first visit the root Node 1, then instead of directly going Left and then Right that is what we do in Binary tree preorder traversal because there is only 2 children, here we don't know the number of child, so what we are going to do is loop for all the child and then do a Preorder traversal for each child.
 
Visit Root Node 1, 
loop for all the children [Node 2, Node 3, Node 4]  (i = 0, i<3; i++) i=0

Visit Node 2, 
Iterate all its children [Node 5, Node 6, Node 7]  (i = 0, i<3; i++) i=0

Visit Node 5,
Iterate all its children []

Node 5 has no children so we came back to Node 2, now i = 1

Came back to Node 2, 
Iterate all its children [Node 5, Node 6, Node 7], (i = 0, i<3; i++), i =2 do for Node 6. 

and it continues.

Java Program to print N-ary tree preorder traversal

package javabypatel;

import java.util.Arrays;

public class NAryTreeTraversal {
    public static void main(String[] args) {
        NAryNode root = new NAryNode(1,
                Arrays.asList(
                        new NAryNode(2, Arrays.asList(
                                    new NAryNode(5),
                                    new NAryNode(6),
                                    new NAryNode(7, Arrays.asList(
                                                new NAryNode(11),
                                                new NAryNode(12))))),
                        new NAryNode(3),
                        new NAryNode(4, Arrays.asList(
                                    new NAryNode(8),
                                    new NAryNode(9),
                                    new NAryNode(10)))
                ));

        preOrderTraversal(root);
    }

    private static void preOrderTraversal(NAryNode start) {
        if (start == null) {
            return;
        }

        System.out.print(start.data + ",");
        if (start.child != null) {
            for (int i = 0; i < start.child.size(); i++) {
                preOrderTraversal(start.child.get(i));
            }
        }
    }
}
NAryNode.java
package javabypatel;

import java.util.List;

public class NAryNode {
    public int data;
    public List<NAryNode> child;

    public NAryNode(int data, List<NAryNode> child) {
        this.data = data;
        this.child = child;
    }
    public NAryNode(int data) {
        this.data = data;
    }
}
at

No comments:

Post a Comment