title: Level Order traversal of a generic tree(n-ary tree) in java
body: <p>(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! )</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Lets make this  a resourceful thread for generic tree implementation. Most of the code is already working. Please help.</p>
  
  <pre><code>Algo:
  </code></pre>
  
  <p>For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.</p>
  
  <pre><code>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-&gt;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
  </code></pre>
  
  <p>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.</p>
  
  <p>1st Attempt:</p>
  
  <pre><code>Queue&lt;NaryTreeNode&gt; BFSqueue = new LinkedList&lt;NaryTreeNode&gt;();
  </code></pre>
  
  <blockquote>
    <p>Error: The type LinkedList is not generic; it cannot be parameterized with arguments </p>
  </blockquote>
  
  <p>2nd Attempt:</p>
  
  <pre><code>QueueList&lt;NaryTreeNode&gt; BFSqueue = new QueueList&lt;NaryTreeNode&gt;();
  </code></pre>
  
  <blockquote>
    <p>Error:  - QueueList cannot be resolved to a type</p>
  </blockquote>
  
  <p>Current Tree Structure for reference:</p>
  
  <pre><code>     root(100)
      /      |       \
    90       50       70
    /        \
  20 30   200  300
  </code></pre>
  
  <p>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.</p>
  
  <pre><code>&gt; 100
  &gt; 90 50 70
  &gt; 20 30 200 300
  </code></pre>
  
  <p>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.</p>
  
  <p>Thanks!</p>
  
  <pre><code>import java.util.*;
  import java.io.*;
  import java.util.List;
  
  //The node for the n-ary tree
  public class NaryTreeNode {
    int data;
    List &lt;NaryTreeNode&gt; nary_list = new ArrayList&lt;NaryTreeNode&gt;();
  }
  
  
  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&lt;NaryTreeNode&gt; temp2 = new ArrayList&lt;NaryTreeNode&gt;();  //Level two first branch
      temp2.add(lev_21);
      temp2.add(lev_22);
  
      List&lt;NaryTreeNode&gt; temp3 = new ArrayList&lt;NaryTreeNode&gt;();  //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&lt;NaryTreeNode&gt; temp = new ArrayList&lt;NaryTreeNode&gt;();  //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);
    }
  }
  </code></pre>