How would you print out the data in a binary tree, level by level, starting at the top?

Question

This is an interview question

I think of a solution. It uses queue.

public Void BFS()    
{   
   Queue q = new Queue();    
   q.Enqueue(root);    
   Console.WriteLine(root.Value);  

   while (q.count > 0)  
   {  
      Node n = q.DeQueue();  
      if (n.left !=null)  
       {  
          Console.Writeln(n.left);  
          q.EnQueue(n.left);  
        }   
       if (n.right !=null)  
       {  
          Console.Writeln(n.right);  
          q.EnQueue(n.right);  
        }   
    }
}

Can anything think of better solution than this, which doesn't use Queue?

Answer 1

Level by level traversal is known as Breadth-first traversal. Using a Queue is the proper way to do this. If you wanted to do a depth first traversal you would use a stack.

The way you have it is not quite standard though. Here's how it should be.

public Void BFS()    
{      
 Queue q = new Queue();
 q.Enqueue(root);//You don't need to write the root here, it will be written in the loop
 while (q.count > 0)
 {
    Node n = q.DeQueue();
    Console.Writeln(n.Value); //Only write the value when you dequeue it
    if (n.left !=null)
    {
        q.EnQueue(n.left);//enqueue the left child
    }
    if (n.right !=null)
    {
       q.EnQueue(n.right);//enque the right child
    }
 }
}

Edit

Here's the algorithm at work. Say you had a tree like so:

     1
    / \
   2   3
  /   / \
 4   5   6

First, the root (1) would be enqueued. The loop is then entered. first item in queue (1) is dequeued and printed. 1's children are enqueued from left to right, the queue now contains {2, 3} back to start of loop first item in queue (2) is dequeued and printed 2's children are enqueued form left to right, the queue now contains {3, 4} back to start of loop ...

The queue will contain these values over each loop

1: {1}

2: {2, 3}

3: {3, 4}

4: {4, 5, 6}

5: {5, 6}

6: {6}

7: {}//empty, loop terminates

Output:

1

2

3

4

5

6

Answer 2

You can avoid a queue by using recursion

TreePrint(node x) {
   Print(x.value); 
   If(x.left != null) TreePrint(x.left);  
   If(x.right != null) TreePrint(x.right);

}

Answer 3

Let's see some Scala solutions. First, I'll define a very basic binary tree:

case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])

We'll use the following tree:

    1
   / \
  2   3
 /   / \
4   5   6

You define the tree like this:

val myTree = Tree(1, 
                  Some(Tree(2, 
                            Some(Tree(4, None, None)), 
                            None
                       )
                  ),
                  Some(Tree(3,
                            Some(Tree(5, None, None)),
                            Some(Tree(6, None, None))
                       )
                  )
             )

We'll define a breadthFirst function which will traverse the tree applying the desired function to each element. With this, we'll define a print function and use it like this:

def printTree(tree: Tree[Any]) = 
  breadthFirst(tree, (t: Tree[Any]) => println(t.value))

printTree(myTree)

Now, Scala solution, recursive, lists but no queues:

def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
  def traverse(trees: List[Tree[T]]): Unit = trees match {
    case Nil => // do nothing
    case _ =>
      val children = for{tree <- trees
                         Some(child) <- List(tree.left, tree.right)} 
                         yield child
      trees map f
      traverse(children)
  }

  traverse(List(t))
}

Next, Scala solution, queue, no recursion:

def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
  import scala.collection.mutable.Queue
  val queue = new Queue[Option[Tree[T]]]
  import queue._

  enqueue(Some(t))

  while(!isEmpty) 
    dequeue match {
      case Some(tree) => 
        f(tree)
        enqueue(tree.left)
        enqueue(tree.right)
      case None =>
    }
}

That recursive solution is fully functional, though I have an uneasy feeling that it can be further simplified.

The queue version is not functional, but it is highly effective. The bit about importing an object is unusual in Scala, but put to good use here.