Traversing Wood

Question

In order to perform a level traversal (BFS) of the common tree, I wrote the following mapping function for the code mentioned in the link below. The problem is that each level is printed twice. Can someone tell me why. The source code without this function can be found in the link below in case someone needs the whole else implementation, just look at the displayBFS function below and tell me why the values ​​are repeated

Level Bypass order of common tree (n-ary tree) in java

Thanks!

void displayBFS(NaryTreeNode n) { Queue<NaryTreeNode> q = new LinkedList<NaryTreeNode>(); if(n!=null) { q.add(n); System.out.println(n.data); } while(n!=null) { for(NaryTreeNode x:n.nary_list) { q.add(x); System.out.println(x.data ); } n = q.poll(); } } 

The structure of the current tree for reference:

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

Conclusion: 100 90 50 70 90 50 70 20 30 200 300 20 30
200
300

Answer 1

The problem is that you process your root node twice: first add it to your turn (on the q.add(n) ), then process it before you go to n = q.poll() , and then get it off the line and process it again.

Everything else is correct, so you only get two copies of each non-root node: doubling happens only once, at the root.

To fix this, delete the q.add(n) (since you are still the root file of the node, even without it), or change this:

  while(n!=null) { ... n = q.poll(); } 

:

  while((n = q.poll()) != null) { ... } 

so that you do not process the root node this is extra time.