How would you print out the data in a binary tree,

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

I tweaked the answer so that it shows the null nodes and prints it by height. Was actually fairly decent for testing the balance of a red black tree. can
also add the color into the print line to check black height.

    Queue<node> q = new Queue<node>();
    int[] arr = new int[]{1,2,4,8,16,32,64,128,256};
    int i =0;
    int b = 0;
    int keeper = 0;
    public void BFS()
    {


        q.Enqueue(root);
        while (q.Count > 0)
        {

            node n = q.Dequeue();

            if (i == arr[b])
            {

                System.Diagnostics.Debug.Write("\r\n"+"("+n.id+")"); 
                b++;
                i =0 ;
            }
            else {

                System.Diagnostics.Debug.Write("(" + n.id + ")"); 

            }
            i++; 


            if (n.id != -1)
            {



                if (n.left != null)
                {

                    q.Enqueue(n.left);
                }
                else
                {
                    node c = new node();
                    c.id = -1;
                    c.color = 'b';
                    q.Enqueue(c);
                }

                if (n.right != null)
                {

                    q.Enqueue(n.right);
                }
                else
                {
                    node c = new node();
                    c.id = -1;
                    c.color = 'b';
                    q.Enqueue(c);

                }
            }

        }
        i = 0;
        b = 0;
        System.Diagnostics.Debug.Write("\r\n");
    }

Answer 2

Try with below code.

public void printLevelOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> nodesToVisit = new LinkedList<>();
    nodesToVisit.add(root);

    int count = nodesToVisit.size();

    while (count != 0) {
        TreeNode node = nodesToVisit.remove();

        System.out.print(" " + node.data);

        if (node.left != null) {
            nodesToVisit.add(node.left);
        }

        if (node.right != null) {
            nodesToVisit.add(node.right);
        }

        count--;

        if (count == 0) {
            System.out.println("");
            count = nodesToVisit.size();
        }
    }
}

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.

Answer 4

C++:

  struct node{
    string key;
    struct node *left, *right;
  };

  void printBFS(struct node *root){
    std::queue<struct node *> q;
    q.push(root);

    while(q.size() > 0){
      int levelNodes = q.size();
      while(levelNodes > 0){
        struct node *p = q.front(); 
        q.pop();
        cout << " " << p->key ;
        if(p->left != NULL) q.push(p->left);
        if(p->right != NULL) q.push(p->right);
        levelNodes--;
      }
      cout << endl;
    }
  }

Input :

Balanced tree created from:

 string a[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n"};

Output:

 g 
 c k 
 a e i m 
 b d f h j l n 

Algorithm:

1. Create an ArrayList of Linked List Nodes.
2. Do the level order traversal using queue(Breadth First Search).
3. For getting all the nodes at each level, before you take out a node from queue, store the size of the queue in a variable, say you call it as levelNodes.
4. Now while levelNodes > 0, take out the nodes and print it and add their children into the queue.
5. After this while loop put a line break.

P.S: I know the OP said, no queue. My answer is just to show if someone is looking for a C++ solution using queue.

Answer 5

Since the question requires printing the tree level by level, there should be a way to determine when to print the new line character on the console. Here's my code which tries to do the same by appending NewLine node to the queue,

void PrintByLevel(Node *root)
{
   Queue q;
   Node *newline = new Node("\n");
   Node *v;
   q->enque(root);
   q->enque(newline);

   while(!q->empty()) {
      v = q->deque();
      if(v == newline) {
         printf("\n");
         if(!q->empty())
            q->enque(newline);
      }
      else {
         printf("%s", v->val);
         if(v->Left)
            q-enque(v->left);
         if(v->right)
            q->enque(v->right);
      }
   }
   delete newline;
}