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?

I'd be surprised if anyone had a solution that was more readable than a BFS of the tree... — Eric, Jul 09 '09 at 15:40
http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal — CodeFusionMobile, Jul 09 '09 at 15:56

score 39 · Accepted Answer · edited Jul 09 '09 at 20:06

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:

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

The OP's code isn't wrong, surely? Writing when you enqueue results in the same order as writing when you dequeue, by definition. Of course your code is DRYer and (hence) better. — Steve Jessop, Jul 09 '09 at 15:59
Yes you're right, the OP code works. I thought I saw an error that wasn't actually there. It's still more proper to only process the node in one place. I've removed my assertion that the OP code was incorrect. — CodeFusionMobile, Jul 09 '09 at 16:18

score 17 · Answer 2 · answered May 05 '12 at 03:53

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;
}

score 5 · Answer 3 · answered Jul 09 '09 at 23:03

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:

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.

kaushal · Answer 4 · 2018-03-02T00:30:52.533

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:

Create an ArrayList of Linked List Nodes.
Do the level order traversal using queue(Breadth First Search).
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.
Now while levelNodes > 0, take out the nodes and print it and add their children into the queue.
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.

score 3 · Answer 5 · edited Nov 12 '14 at 08:00

public class LevelOrderTraversalQueue {     

    Queue<Nodes> qe = new LinkedList<Nodes>();

    public void printLevelOrder(Nodes root)     
    { 
        if(root == null) return;

        qe.add(root);
        int count = qe.size();

        while(count!=0)
        {   
            System.out.print(qe.peek().getValue());
            System.out.print("  ");
            if(qe.peek().getLeft()!=null) qe.add(qe.peek().getLeft());
            if(qe.peek().getRight()!=null) qe.add(qe.peek().getRight());
            qe.remove(); count = count -1;
            if(count == 0 )
            {
                System.out.println("  ");
                count = qe.size();
            }
        }           
    }

}

Faruk Sahin · Answer 6 · 2012-07-25T09:48:50.137

In order to print out by level, you can store the level information with the node as a tuple to add to the queue. Then you can print a new line whenever the level is changed. Here is a Python code to do so.

from collections import deque
class BTreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def printLevel(self):
        """ Breadth-first traversal, print out the data by level """
        level = 0
        lastPrintedLevel = 0
        visit = deque([])
        visit.append((self, level))
        while len(visit) != 0:
            item = visit.popleft()
            if item[1] != lastPrintedLevel:  #New line for a new level
                lastPrintedLevel +=1
                print
            print item[0].data,
            if item[0].left != None:
                visit.append((item[0].left, item[1] + 1))
            if item[0].right != None: 
                visit.append((item[0].right, item[1] + 1))

score 1 · Answer 7 · answered Sep 03 '15 at 23:08

Try this one (Complete code) :

class HisTree
{
    public static class HisNode
    {
        private int data;
        private HisNode left;
        private HisNode right;

        public HisNode() {}
        public HisNode(int _data , HisNode _left , HisNode _right)
        {
            data = _data;
            right = _right;
            left = _left;
        }
        public HisNode(int _data)
        {
            data = _data;
        }
    }

    public static int height(HisNode root)
    {
        if (root == null)
        {
            return 0;
        }

        else
        {
            return 1 + Math.max(height(root.left), height(root.right));
        }
    }


    public static void main(String[] args)
    {
//          1
//         /  \ 
//        /    \
//       2      3
//      / \    / \  
//     4    5 6   7
//    /
//   21

        HisNode root1 = new HisNode(3 , new HisNode(6) , new HisNode(7));
        HisNode root3 = new HisNode(4 , new HisNode(21) , null);
        HisNode root2 = new HisNode(2 , root3 , new HisNode(5));
        HisNode root = new HisNode(1 , root2 , root1);
        printByLevels(root);
    }


    private static void printByLevels(HisNode root) {

        List<HisNode> nodes = Arrays.asList(root);
        printByLevels(nodes);

    }

    private static void printByLevels(List<HisNode> nodes)
    {
        if (nodes == null || (nodes != null && nodes.size() <= 0))
        {
            return;
        }
        List <HisNode> nodeList = new LinkedList<HisNode>();
        for (HisNode node : nodes)
        {
            if (node != null)
            {
                System.out.print(node.data);
                System.out.print(" , ");
                nodeList.add(node.left);
                nodeList.add(node.right);
            }
        }
        System.out.println();
        if (nodeList != null && !CheckIfNull(nodeList))
        {
            printByLevels(nodeList);    
        }
        else
        {
            return;
        }

    }


    private static boolean CheckIfNull(List<HisNode> list)
    {
        for(HisNode elem : list)
        {
            if (elem != null)
            {
                return false;
            }
        }
        return true;
    }
}

score 1 · Answer 8 · answered Jul 06 '18 at 05:19

I think what you expecting is to print the nodes at each level either separated by a space or a comma and the levels be separated by a new line. This is how I would code up the algorithm. We know that when we do a breadth-first search on a graph or tree and insert the nodes in a queue, all nodes in the queue coming out will be either at the same level as the one previous or a new level which is parent level + 1 and nothing else.

So when you are at a level keep printing out the node values and as soon as you find that the level of the node increases by 1, then you insert a new line before starting to print all the nodes at that level.

This is my code which does not use much memory and only the queue is needed for everything.

Assuming the tree starts from the root.

queue = [(root, 0)]  # Store the node along with its level. 
prev = 0
while queue:
  node, level = queue.pop(0)
  if level == prev:
    print(node.val, end = "")
  else:
    print()
    print(node.val, end = "")
  if node.left:
    queue.append((node.left, level + 1))
  if node.right:
    queue.append((node.right, level + 1))
  prev = level

At the end all you need is the queue for all the processing.

score 0 · Answer 9 · answered Jun 01 '15 at 22:16

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");
    }

score 0 · Answer 10 · answered Apr 02 '17 at 08:01

Of course you don't need to use queue. This is in python.

# Function to  print level order traversal of tree
def printLevelOrder(root):
    h = height(root)
    for i in range(1, h+1):
        printGivenLevel(root, i)


# Print nodes at a given level
def printGivenLevel(root , level):
    if root is None:
        return
    if level == 1:
        print "%d" %(root.data),
    elif level > 1 :
        printGivenLevel(root.left , level-1)
        printGivenLevel(root.right , level-1)


""" Compute the height of a tree--the number of nodes
    along the longest path from the root node down to
    the farthest leaf node
"""
def height(node):
    if node is None:
        return 0
    else :
        # Compute the height of each subtree 
        lheight = height(node.left)
        rheight = height(node.right)
        return max(lheight, reight)

score 0 · Answer 11 · edited Aug 28 '18 at 06:13

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();
        }
    }
}

score 0 · Answer 12 · answered Jul 16 '19 at 11:57

here is my answer.

//for level order traversal
    func forEachLevelOrder(_ visit : (TreeNode) -> Void) {

        visit(self)
        var queue = Queue<TreeNode>()
        children.forEach {
            queue.Enqueue($0)
        }
        while let node = queue.Dequeue() {
            visit(node)
            node.children.forEach { queue.Enqueue($0)}
        }

    }

children is an array here that stores the children of a node.

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

12 Answers12

Linked