2
\$\begingroup\$

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);
}
\$\endgroup\$
4
\$\begingroup\$

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<>();
    }
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.