How to do a Level Order Traversal?

Question

I'm trying to do a linear order traversal on a binary tree but having trouble getting the correct output. Basically I have created a queue and start by enqueuing the root, then until the queue is empty I dequeue the first element and add its children to the end of the queue. When dequeuing it returns a generic element (). I have a problem in converting this element to a tree node so that I can enqueue its children to the end of the queue in the next step. Here's what I have done so far:

public void levelOrderTraversal()
{
    NodeQueue<E> queue = new NodeQueue<E>();
    BTPosition<E> current = root;
    queue.enqueue(current.element());
    E temp = null;

    while(!queue.isEmpty())
    {
        temp = queue.dequeue();
        System.out.println(temp.toString());
        current.setElement(temp);

        if (hasLeft(current))
        {
            queue.enqueue(left(current).element());
        }
        if (hasRight(current))
        {
            queue.enqueue(right(current).element());
        }
    }
}

API for BTPosition and NodeQueue can be found in http://net3.datastructures.net/doc4/index.html?net/datastructures/

Any suggestions are really appreciated..

Answer 1

You'll want the Queue to be of type BTPosition<E>. <E> is simply the object type, for instance Integer or String. BTPosition appears to be the actual node in your binary tree.

public void levelOrderTraversal()
{
    NodeQueue<BTPosition<E>> queue = new NodeQueue<BTPosition<E>>(); 
    BTPosition<E> current = root;
    queue.enqueue(current); 

    while(!queue.isEmpty())
    {
        current = queue.dequeue();
        System.out.println(temp.element().toString());

        if (current.getLeft() != null)
        {
            queue.enqueue(current.getLeft());
        }
        if (current.getRight() != null)
        {
            queue.enqueue(current.getRight());
        }
    }
}