Level Order tree Traversal for a generic tree, displaying the tree level by level

Question

I would like to display the tree structure level by level. My current code does a BFS or Level Order Traversal but I cannot get the output to display the tree structure like a tree See current output and Expected output.

My idea was to use some kind of count to iterate over elements from the same level in the queue.

How can I do so.

Original Code without this function can be found in the link below in case someone needs the entire implementation else just look at the displayBFS function below.

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

Thanks!

   void displayBFS(NaryTreeNode n)
   {
      Queue<NaryTreeNode> q  = new LinkedList<NaryTreeNode>();
      System.out.println(n.data);

       while(n!=null)
     {   
         for(NaryTreeNode x:n.nary_list)
         {
             q.add(x);
             System.out.print(x.data + " ");
         }
         n=q.poll();
         System.out.println();
      } 
  }

Current Tree Structure for reference:

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


    Current Output:
        100
        90 50 70
        20 30
        200 300

    Expected Output
        100
        90 50 70
        20 30 200 300    

Also, I had posted a logic issue with the same function earlier, as that was answered and the current question realtes to a different problem, I posted a new question, is this approach okay or should I make edits to the earlier question and not open a new one?

Answer 1

only need to keep track of current level and next level.

static void displayBFS(NaryTreeNode root) {
    int curlevel = 1;
    int nextlevel = 0;

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

    while(!queue.isEmpty()) { 
        NaryTreeNode node = queue.remove(0);

        if (curlevel == 0) {
            System.out.println();
            curlevel = nextlevel;
            nextlevel = 0;
        }

        for(NaryTreeNode n : node.nary_list) {
            queue.addLast(n);
            nextlevel++;
        }

        curlevel--;
        System.out.print(node.data + " ");
    } 
}

when you switch levels, swap nextlevel for currentlevel and reset nextlevel. i prefer the simplicity of this over keeping a whole separate queue.

i had this question for a microsoft interview last week... it didn't go so well for me over the phone. good on you for studying it.