Level-order tree traversal

Question

Hi. I am trying to write a method that will take an IntTree as a parameter and return a Queue with the values of the IntTree in level order. To clarify: an IntTree is a tree with an integer value as its root, and has an IntTree as its left and right subtrees. A note on some methods: value(t) - returns the integer value at the root of the tree left(t) - returns the left IntTree subtree // right(t) - returns the right sub-tree

Here's the code I have so far. I'm rather new to programming, so I'm sorry if it's not very elegant.

public static QueueList levelOrder(IntTree t) {
//returns a QueueList with the values in level order

Object val;
QueueList q = new QueueList(); //temp queueList
QueueList theta = new QueueList();  //the QueueList which will eventually be printed


if (isEmpty(t)) {
  return theta;    //possible problem here
} else {

  IntTree tL = left(t);  //using for possible updating. probably won't work
  IntTree tR = right(t);

  q.enqueue(value(t)); //enqueue the root of the tree

  while (!q.isEmpty()) {
    val = q.dequeue();  //pop off the top element for printing
    theta.enqueue(val); // put the element in the queue to be printed
    if (tL != null) { 
      q.enqueue(value(tL));  //if the left isn't null, enqueue the lefts
      tL = left(tL); //this will only branch left

    }
    if (tR != null) {       //if the right isn't null, enqueue the rights
      q.enqueue(value(tR));
      tR = right(tR);  //this will only branch right
    }
  }
}
return theta; //returns a queue with values in order

}

I wrote the tL and tR variables because if I wrote something like "if (left(t) != null)", I would end up with infinite recursion, since 't' was never updated. The problem with this code is that 'tL' will only branch left and 'tR' will only branch right. So after one level below the root, some values will never be stored. I hope this was clear, and any help is greatly appreciated. Thank you.

Answer 1

Instead of implementing the fringe as a queue of values, implement it as a queue of IntTrees (nodes). That will simplify your logic tremendously.

  while (!q.isEmpty()) {
    IntTree node = q.dequeue();  //pop off the top element
    theta.enqueue(value(node)); // put the element in the queue to be printed

    //enqueue the children
    IntTree left = left(node);
    if ( left != null ) {
        q.enqueue(left);
    }
    //...similar for right
  }

When you have this you don't have to maintain the tL and tR pointers in parallel, which I imagine is a flawed approach anyhow.

Links

• Breadth-First Traversal (Wikipedia)