Order tree level Bypass for the general tree, showing the level of the tree by level

Question

I would like to display the level of the tree structure by level. My current code traverses BFS or Level Order Traversal, but I cannot get output to display a tree structure such as a tree. See Current Output and Expected Result.

My idea was to use some sort of counting to iterate over elements from one level in the queue.

How can i do this.

The source code without this function can be found in the link below, if someone needs the entire else implementation, just look at the displayBFS function below.

Level Bypass order of common 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 

In addition, I previously sent a logical problem with the same function, since this was answered, and the current question is real to another problem, I posted a new question, is this approach suitable or should I make changes to the previous question and not open a new one?

Answer 1

you only need to track the current level and the 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, change the next level to the current level and reset to the next level. I prefer the simplicity of this while keeping a whole separate queue.

I had this question for an interview with Microsoft last week ... for me it was not so good on the phone. good for you to study it.

Answer 2

The simplest solution I know about this problem is to use a sentinel. The queue is initialized with the root node, followed by a watch, and then you loop the queue:

• remove front element
• if it's a sentinel:
  • we are at the end of the level, so we can end the output line
  • If the queue is not empty, click on it at the end of the queue.
• if it is not sentinel:
  • print out
  • put all your children in the queue.

I do not deal with Java, but I have C ++ code for BFS with depth that I trimmed to complete this print task:

 void show_tree_by_levels(std::ostream& os, Node* tree) { Node* sentinel = new Node; std::deque<Node*> queue{tree, sentinel}; while (true) { Node* here = queue.front(); queue.pop_front(); if (here == sentinel) { os << std::endl; if (queue.empty()) break; else queue.push_back(sentinel); } else { for (Node* child = here->child; child; child = child->sibling) queue.push_back(child); os << here->value << ' '; } } } 

Note that I prefer to use a two-pointer solution (first_child / next_sibling), because it usually works simpler than inline lists. YMMV.

Answer 3

Use another queue to indicate the depth. The code below is not tested, but it should give you an idea (the sep variable is introduced to avoid lagging spaces):

 void displayBFS(NaryTreeNode n) { Queue<NaryTreeNode> q = new LinkedList<NaryTreeNode>(); Queue<Integer> depth = new LinkedList<Integer>(); q.add(n); depth.add(0); String sep = ""; int oldDepth = 0 while(!q.isEmpty()) { NaryTreeNode currN = q.poll(); int currDepth = depth.poll(); if (currDepth > oldDepth) { System.out.println(); oldDepth = currDepth; sep = ""; } System.out.print(sep + currN.data); sep = " "; for(NaryTreeNode x : currN.nary_list) { q.add(x); depth.add(currDepth + 1); } } } 

In my opinion, this approach is more understandable compared to other methods that could be done.

Answer 4

I think we need three more variables. numInCurrentLevel for tracking the number of items at the current level, indexInCurrentLevel for tracking when traversing the current level, and numInNextLevel for tracking the number of items at the next level. Code below:

 static void displayBFS(NaryTreeNode root) { Queue<NaryTreeNode> q = new LinkedList<NaryTreeNode>();; q.add(root); int numInCurrentLevel = 1; int numInNextLevel = 0; int indexInCurrentLevel=0; while(!q.isEmpty()) { NaryTreeNode node = q.poll(); System.out.print(node.data + " "); indexInCurrentLevel++; for(NaryTreeNode n : node.nary_list) { q.add(n); numInNextLevel++; } //finish traversal in current level if(indexInCurrentLevel==numInCurrentLevel) { System.out.println(); numInCurrentLevel=numInNextLevel; numInNextLevel=0; indexInCurrentLevel=0; } } } 

Hope this helps, I'm not very familiar with Java programming.