Java Printing a Binary Tree using Level-Order in a Specific Format

Question

Okay, I have read through all the other related questions and cannot find one that helps with java. I get the general idea from deciphering what i can in other languages; but i am yet to figure it out.

Problem: I would like to level sort (which i have working using recursion) and print it out in the general shape of a tree.

So say i have this:

    1 
   / \
  2   3
 /   / \
4   5   6

My code prints out the level order like this:

1 2 3 4 5 6

I want to print it out like this:

1
2 3
4 5 6

Now before you give me a moral speech about doing my work... I have already finished my AP Comp Sci project and got curious about this when my teacher mentioned the Breadth First Search thing.

I don't know if it will help, but here is my code so far:

/**
  * Calls the levelOrder helper method and prints out in levelOrder.
  */
 public void levelOrder()
 {
  q = new QueueList();
  treeHeight = height();
  levelOrder(myRoot, q, myLevel);
 }

 /**
  * Helper method that uses recursion to print out the tree in 
  * levelOrder
  */
 private void levelOrder(TreeNode root, QueueList q, int curLev)
 {
  System.out.print(curLev);
  if(root == null)
  {
   return;
  }

  if(q.isEmpty())
  {
   System.out.println(root.getValue());
  }
  else
  {
   System.out.print((String)q.dequeue()+", ");
  }

  if(root.getLeft() != null)
  {
   q.enqueue(root.getLeft().getValue());
   System.out.println();
  }
  if(root.getRight() != null)
  {
   q.enqueue(root.getRight().getValue());
   System.out.println();
   curLev++;
  }

  levelOrder(root.getLeft(),q, curLev);
  levelOrder(root.getRight(),q, curLev);
 }

From what i can figure out, i will need to use the total height of the tree, and use a level counter... Only problem is my level counter keeps counting when my levelOrder uses recursion to go back through the tree.

Sorry if this is to much, but some tips would be nice. :)

Answer 1

Here is the code, this question was asked to me in one of the interviews...

public void printTree(TreeNode tmpRoot) {

        Queue<TreeNode> currentLevel = new LinkedList<TreeNode>();
        Queue<TreeNode> nextLevel = new LinkedList<TreeNode>();

        currentLevel.add(tmpRoot);

        while (!currentLevel.isEmpty()) {
            Iterator<TreeNode> iter = currentLevel.iterator();
            while (iter.hasNext()) {
                TreeNode currentNode = iter.next();
                if (currentNode.left != null) {
                    nextLevel.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    nextLevel.add(currentNode.right);
                }
                System.out.print(currentNode.value + " ");
            }
            System.out.println();
            currentLevel = nextLevel;
            nextLevel = new LinkedList<TreeNode>();

        }

    }