Print binary tree level by level

Question

Please critique:

public void printTree(Node head) {
 if (head == null)
 return;
 Queue<Node> q1 = new PriorityQueue<Node>();
 Queue<Node> q2 = new PriorityQueue<Node>();
 q1.add(head);
 do {
 while (q1.size() > 0) {
 Node element = q1.poll();
 System.out.print(element.data + " ");
 if (element.left != null)
 q2.add(element.left);
 if (element.right != null)
 q2.add(element.right);
 }
 System.out.println();
 while (q2.size() > 0) {
 q1.add(q2.poll());
 }
 q2.clear();
 } while (q1.size() > 0);
}

Answer 1

Your Node type should really be generic with Node<T>, so that you could easily store a Node<Integer>, Node<Double>, Node<BigInteger>, Node<String>, etc.

---

The function printTree accesses no external state. As such, I'd recommend it be made a static function:

public static void <T> printTree(Node<T> head) {

---

When I see Queue<Node>, I imagine a LIFO data structure. Priority queues are not LIFO, so if you really want a priority queue, I'd actually say PriorityQueue<Node> q1 = new PriorityQueue<Node>(); However, this is up to preference; in general, it is good form to use Queue<Node>.

On the other hand, you may be simply looking for a queue datatype. In that case, you want ArrayDeque<Node>.

---

q1.size() > 0

Replace that with !q1.isEmpty(). It reads better.

---

while (q2.size() > 0) {
 q1.add(q2.poll());
}
q2.clear();

What you are doing here is actually simply

q1.addAll(q2);
q2.clear();

---

Putting this all together:

public static void <T> printTree(Node<T> head) {
 if (head == null)
 return;
 Queue<Node<T>> q1 = new ArrayDeque<>(); // Type name can be left out here Java 7+
 Queue<Node<T>> q2 = new ArrayDeque<>();
 q1.add(head);
 do {
 while (!q1.isEmpty()) {
 Node<T> element = q1.poll();
 System.out.print(element.data + " ");
 if (element.left != null)
 q2.add(element.left);
 if (element.right != null)
 q2.add(element.right);
 }
 System.out.println();
 q1.addAll(q2);
 q2.clear();
 } while (!q1.isEmpty());
}

---

There are several options for improvements once you reach here. One is to create a separate Iterator<Node<T>> for your nodes, then just iterate over the iterator printing each node. But I'd also prefer this code:

public static void <T> printTree(Node<T> head) {
 if (head == null)
 return;
 Queue<Node<T>> q1 = new ArrayDeque<>(); // Type name can be left out here Java 7+
 Queue<Node<T>> q2 = new ArrayDeque<>();
 q1.add(head);
 // while loops are more common; there is no change in functionality, but may be easier to read.
 while (!q1.isEmpty()) {
 for (Node<T> element : q1) { // This is a for each loop
 System.out.print(element.data + " ");
 if (element.left != null)
 q2.add(element.left);
 if (element.right != null)
 q2.add(element.right);
 }
 System.out.println();
 q1 = q2; // garbage collection isn't *too* expensive, and we get more expressive this way.
 q2 = new ArrayDeque<>();
 }
}

Answer 2

Only one queue required

If you loop over the number of elements at each level, you can use a single queue to solve the problem:

public void printTree(Node head) {
 if (head == null)
 return;
 Queue<Node> q = new ArrayDeque<>();
 q.add(head);
 do {
 int size = q.size();
 for (int i=0; i<size; i++) {
 Node element = q.poll();
 System.out.print(element.data + " ");
 if (element.left != null)
 q.add(element.left);
 if (element.right != null)
 q.add(element.right);
 }
 System.out.println();
 } while (q.size() > 0);
}

Also notice I used an ArrayDeque because as Justin pointed out, a PriorityQueue is inappropriate for this program.