Printing the values on each level of a Binary Tree

Question

The below code is for printing level-by-level in a binary tree:

//level order printing
public static void levelOrderPrint(Node root){
 Queue<Node> que = new LinkedList<Node>();
 Node mark = new Node(0);
 if(root != null){
 que.add(root);
 que.add(mark);
 }
 while(!que.isEmpty()){
 Node temp = que.poll();
 if(temp != mark)
 System.out.print(temp.key);
 if(temp == mark){
 if(que.peek() == mark || que.isEmpty()){
 return;
 }
 que.add(mark);
 System.out.println();
 }
 if(temp.left != null){
 que.add(temp.left);
 }
 if(temp.right != null){
 que.add(temp.right);
 }
 }
}

I would like to know if there are any bugs or possible optimizations.

• Marc-Andre: Hi and welcome to Code Review! To the best of your knowledge does this code works ? We won't review your code if you think there is bug in it, but if you think all your code works as expected we will happily review your code!

Answer 1

This is good code.

General

While it does what it says it will do, here is one beef I have with it, but it's a small one:

 Node temp = que.poll();
 if(temp != mark)
 System.out.print(temp.key);

No braces, no indenting, code meaning is confused.....

That should be:

 Node temp = que.poll();
 if(temp != mark) {
 System.out.print(temp.key);
 }

There is a fair amount of debate about using '1-liner' if statements. The following are reasons why I despise them:

• the meaning of the code becomes white-space defined (like your indenting problem above). There are whole languages ( cough Pythong cough ) which are defined by whitespace. Java is defined by braces {}. Use them.
• If you use a version-control-system like CVS, SVN, Git, etc. then small changes to code blocks can become visually big in a change-log. Adding one line to the code means updating 3 lines.
• it can lead to bugs where people do not put braces in to lines where there should be two statements.
• etc.
• etc.

I don't like 1-liners Sam-I-Am

OK. But, as code goes, yours is good. How can it be better?

Improvements

• You can make mark a private static final instance:

  private static final Node MARK = new Node(0);
  

• The following statement has redundancy:

   if(que.peek() == mark || que.isEmpty()){
   return;
   }
  

  it could be:

   if(que.isEmpty()){
   return;
   }
  

  It is not possible for the queue to have two consecutive marks, so the peek can never be a mark.

• Now, back to that indentation on the println() method call... here's your code:

   if(temp != mark)
   System.out.print(temp.key);
   if(temp == mark){
   if(que.peek() == mark || que.isEmpty()){
   return;
   }
   que.add(mark);
   System.out.println();
   }
  

  if you had correct braces, etc. you would see that you would be better off with an if/else condition, and that will save an if check:

   if(temp != mark) {
   System.out.print(temp.key);
   } else {
   if(que.peek() == mark || que.isEmpty()){
   return;
   }
   que.add(mark);
   System.out.println();
   }
  

• System.out.println(...) and all the print*(...) variants are slow (they are synchronized). Your code would be faster if you used a system like:

  StringBuilder sb = new StringBuilder();
  ....
   if (temp != mark) {
   sb.append(temp.key);
   } else {
   ....
   sb.append("\n");
   }
  ....
  System.out.print(sb);
  

Conclusion

Otherwise, this is good code.