Printing a BST tree level-by-level

Question

Please review and tell me what improvements can be made:

package trees;

import java.util.LinkedList;
import java.util.Queue;

public class PrintBSTLevelByLevel {


     public static class Node {

        int data;
        Node left;
        Node right;

        Node(int val){

            this.data = val;
            Node left = null;
            Node right = null;

        }
    }

      public void LevelOrderQueue(Node root){

          Queue q = new LinkedList();
          int levelNodes = 0;

          if(root == null) return;
          q.add(root);

          while(!q.isEmpty()){

              levelNodes = q.size();

              while (levelNodes > 0){

                  Node n = (Node)q.remove();
                  System.out.println(""+n.data);
                  if(n.left!= null)
                      q.add(n.left);
                  if(n.right!=null)
                      q.add(n.right);
                  levelNodes--;

              }
              System.out.println("");




          }



          //return null;
      }

    public static void main(String[] args) {

        Node root = new Node(5);

        root.left = new Node(10);
        root.right = new Node(15);
        root.left.left = new Node(20);
        root.left.right = new Node(25);
        root.right.left = new Node(30);
        root.right.right = new Node(35);

        PrintBSTLevelByLevel l = new PrintBSTLevelByLevel();

        System.out.println(" Output by Better Approach : ");
        l.LevelOrderQueue(root);




    }




}

Answer 1

Though your code would suffice for the current task, I would create a fully (or partially) functioning Tree class, so that it may be used later. Another class will handle the display. This is what the Tree class would look like:

public class Tree<T> {

    private Node rootNode;

    public Tree() {
        rootNode = null;
    }

    public Tree(T rootValue) {
        rootNode = new Node(rootValue);
    }

    public Node getRootNode() {
        return rootNode;
    }

    public Node createNewNode(T value) {
        return new Node(value);
    }

    class Node {

        private T value;
        public Node left = null;
        public Node right = null;

        Node(T value) {
            this.value = value;
        }

        public T getValue() {
            return value;
        }

        public void setValue(T value) {
            this.value = value;
        }

    }

}

This is an extremely basic Tree class that has very basic functions, but it gets the job done. Later, when you need more functions for the Tree class, you can easily go and add it. Explanation of the class:

• The default constructor (Tree()) will just set the root node to null.
• The other constructor will take the argument and create a new Node with the value of the argument.
• The getRootNode() method is to get the root Node, so that you can get the other Nodes like so:

// example
Tree tree = new Tree(10);
// initialization of values
Node someNode = tree.getRootNode().left.right/*etc*/;

• The createNewNode(T value) method provides indirect access to the otherwise inaccessible (at least outside the package) Node(T value) constructor. Though this isn't necessary, as you can make the Node's constructor public, it is good practice for later.
• The Node class is a simple class that represents a node with a left and right node, as well as its value:
  • The value is a private variable, so getters and setters are required to access it. Again, though you can just make value public, it is better practice not do so.
  • I made the left and right variables public, just for easier usage. Though it differs from good practice, there are some cases where there are exceptions (some programmers may disagree with this statement).

Now, for the printing component:

Since I redesigned the Tree class completely, we have to change your method as well. Just to do exactly what your code does, here is the new method:

public <T> void LevelOrderQueue(Tree<T> tree) {
    if (tree != null) {
        Tree<T>.Node rootNode = tree.getRootNode();
        if (rootNode != null) {
            Queue<Tree<T>.Node> queue = new LinkedList<>();
            int levelNodes = 0;
            queue.add(rootNode);
            while (!queue.isEmpty()) {
                levelNodes = queue.size();
                while (levelNodes > 0) {
                    Tree<T>.Node node = queue.remove();
                    System.out.println(node.getValue());
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                    levelNodes--;
                }
                System.out.println();
            }
        }
    }

}

Note some changes:

• The method now takes a Tree<T> object instead of a Node object.
• This method has two checks for null; the first one to check for the tree, and the second one for the root node.
• I added braces for if statements. The reason for this is because the lack of braces may cause horrible, hard-to-spot bugs that might frustrate you for days. I can't find the post which I wrote about this in more detail, but I will post it up once I find it. (EDIT: Found it! Read here)
• I added generics to your Queue initialization.
• I removed the Node cast. This is not necessary when generics are used.
• I changed naming. Variable names like node and queue are easier to understand than n and q.
• I changed System.out.println(""); to System.out.println();. There is a println() method that takes no arguments.
• I changed System.out.println(""+n.data); to System.out.println(node.value);. The beginning "" is not necessary because System.out.println() automatically converts what is given into a String, via the toString() method defined by the class (or whatever class before it in the inheritance chain that has it defined).
• I added more space between some individual keywords, variable names, braces, parentheses etc.: this is for better readability, and to follow the Java conventions. If you are not sure of them, just search up "Java Conventions" on google.
• I removed empty lines. You may re-add them where you like them; I like my code that way.