Level Order traversal of a generic tree(n-ary tree) in java

Question

(In case you want to avoid the lengthy explanation, all I am looking for is a level order traversal for a generic-tree(n-ary tree) in java. The code supplied works and needs the level order display function. Looked around for an hour but couldnt find reference to generic n-ary trees. Would appreciate if soemone can help me build the LevelOrderDisplay function on top of my code as it will help me understand the queue error that I am getting. Thanks! )

I have been trying to implement a tree representation of Autosys job schedules at work. As each job(process) can have one or or more dependent job on them, i decided to go with a n-ary tree implementation so that i can map the flow. I am using java collections for the same. I need to perform a level order traversal to display job dependencies. First Print Root, then all nodes on level one and then all nodes on level 2 and so on.

I tried to search for over an hour on StackOverflow but most the examples I came across were for Binary Trees. I do understand that I need to use a queue for this.

From what i got during my research, the algorithm should look like: Please correct me if this is wrong and if possible, provide a code for this. Alternate approaches are also welcome but what I am really looking for is a simple elementary level order traversal of a generic tree.

Lets make this a resourceful thread for generic tree implementation. Most of the code is already working. Please help.

Algo:

For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.

printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
    a) print temp_node->data.
    b) Enqueue temp_node’s children (first left then right children) to q
    c) Dequeue a node from q and assign it’s value to temp_node

For some strange reason, I have not been able to declare a queue in my Eclipse IDE. I have imported java.util.*; I am missing something here, please have a look at the below errors.

1st Attempt:

Queue<NaryTreeNode> BFSqueue = new LinkedList<NaryTreeNode>();

Error: The type LinkedList is not generic; it cannot be parameterized with arguments

2nd Attempt:

QueueList<NaryTreeNode> BFSqueue = new QueueList<NaryTreeNode>();

Error: - QueueList cannot be resolved to a type

Current Tree Structure for reference:

     root(100)
    /      |       \
  90       50       70
  /        \
20 30   200  300

The output of the current display function is in pre order: 100 90 20 30 50 200 300 70 I need a level order traversal for the same. Required output.

> 100
> 90 50 70
> 20 30 200 300

This is a working code if someone wants to run it on their machine and add the level order traversal function. Please provide commented explanation for the queue operations as that is where I am stuck.

Thanks!

import java.util.*;
import java.io.*;
import java.util.List;

//The node for the n-ary tree
public class NaryTreeNode {
  int data;
  List <NaryTreeNode> nary_list = new ArrayList<NaryTreeNode>();
}


public class NaryTree {

  void display(NaryTreeNode t) {
    if(t==null)
      return;

    System.out.print(t.data + " ");

    for(NaryTreeNode n : t.nary_list) 
          display(n) ;            //Recursive Call
 }


  public static void main(String args[]){

    NaryTree t1 = new NaryTree();

    NaryTreeNode root = new NaryTreeNode();

    root.data = 100;

    NaryTreeNode lev_11 = new NaryTreeNode();   lev_11.data=90;
    NaryTreeNode lev_12 = new NaryTreeNode();   lev_12.data=50;
    NaryTreeNode lev_13 = new NaryTreeNode();   lev_13.data=70;
    NaryTreeNode lev_21 = new NaryTreeNode();   lev_21.data=20;
    NaryTreeNode lev_22 = new NaryTreeNode();   lev_22.data=30;
    NaryTreeNode lev_23 = new NaryTreeNode();   lev_23.data=200;
    NaryTreeNode lev_24 = new NaryTreeNode();   lev_24.data=300;

    //Add all the nodes to a list.

    List<NaryTreeNode> temp2 = new ArrayList<NaryTreeNode>();  //Level two first branch
    temp2.add(lev_21);
    temp2.add(lev_22);

    List<NaryTreeNode> temp3 = new ArrayList<NaryTreeNode>();  //level two second branch
    temp3.add(lev_23);
    temp3.add(lev_24);

    lev_11.nary_list.addAll(temp2);
    lev_12.nary_list.addAll(temp3);

    List<NaryTreeNode> temp = new ArrayList<NaryTreeNode>();  //level one
    temp.add(lev_11);
    temp.add(lev_12);
    temp.add(lev_13);


    // Add Temp to root  to form a leaf of the root
    root.nary_list.addAll(temp);

    // root=null;
    //Call the display function.
    t1.display(root);
  }
}

Answer 1

Level-order traversal using Queue:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;
import java.util.stream.Collectors;

public class LevelOrderTraversal {
    static class Node {
        int data;

        Node children[];

        Node(int data, int n) {
            children = new Node[n];
            this.data = data;
        }
    }

    public static void main(String[] args) {
        /*  
                       1 
                    /  |  \ 
                   2   3   4 
                 / | \ 
                5  6  7 
        */
        int n = 3;
        Node root = new Node(1, n);
        root.children[0] = new Node(2, n);
        root.children[1] = new Node(3, n);
        root.children[2] = new Node(4, n);
        root.children[0].children[0] = new Node(5, n);
        root.children[0].children[1] = new Node(6, n);
        root.children[0].children[2] = new Node(7, n);

        List<List<Integer>> levelList = levelOrder(root);
        for (List<Integer> level : levelList) {
            for (Integer val : level) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> levelList = new ArrayList<>();

        if (root == null) {
            return levelList;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int n = queue.size();
            List<Integer> level = new ArrayList<>();

            while (n-- > 0) {
                Node node = queue.remove();
                level.add(node.data);
                queue.addAll(Arrays.stream(node.children).filter(Objects::nonNull).collect(Collectors.toList()));
            }
            levelList.add(level);
        }
        return levelList;
    }

}

Answer 2

The following seems to work. For extra credit, iteration can be done with an enhanced for loop, and aborted at any time. You might want to add access modifiers.

import java.util.*;

class NaryTree {
    final int data;
    final List<NaryTree> children;

    public NaryTree(int data, NaryTree... children) {
        this.data = data;
        this.children = Arrays.asList(children);
    }

    static class InOrderIterator implements Iterator<Integer> {
        final Queue<NaryTree> queue = new LinkedList<NaryTree>();

        public InOrderIterator(NaryTree tree) {
            queue.add(tree);
        }

        @Override
        public boolean hasNext() {
            return !queue.isEmpty();
        }

        @Override
        public Integer next() {
            NaryTree node = queue.remove();
            queue.addAll(node.children);
            return node.data;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    Iterable<Integer> inOrderView = new Iterable<Integer>() {
        @Override
        public Iterator<Integer> iterator() {
            return new InOrderIterator(NaryTree.this);
        } 
    };
}

Test code:

public class Test {
    public static void main(String[] args) throws Exception {
        NaryTree tree = new NaryTree(100,
            new NaryTree(90, 
                new NaryTree(20),
                new NaryTree(30)
            ), new NaryTree(50, 
                new NaryTree(200),
                new NaryTree(300)
            ), new NaryTree(70)
        );
        for (int x : tree.inOrderView) {
            System.out.println(x);
        }
    }
}