# Programming Interview Questions 20: Tree Level Order Print

Given a binary tree of integers, print it in level order. The output will contain space between the numbers in the same level, and new line between different levels. For example, if the tree is:

The output should be:
1
2 3
4 5 6

It won’t be practical to solve this problem using recursion, because recursion is similar to depth first search, but what we need here is breadth first search. So we will use a queue as we did previously in breadth first search. First, we’ll push the root node into the queue. Then we start a while loop with the condition queue not being empty. Then, at each iteration we pop a node from the beginning of the queue and push its children to the end of the queue. Once we pop a node we print its value and space.

To print the new line in correct place we should count the number of nodes at each level. We will have 2 counts, namely current level count and next level count. Current level count indicates how many nodes should be printed at this level before printing a new line. We decrement it every time we pop an element from the queue and print it. Once the current level count reaches zero we print a new line. Next level count contains the number of nodes in the next level, which will become the current level count after printing a new line. We count the number of nodes in the next level by counting the number of children of the nodes in the current level. Understanding the code is easier than its explanation:

```class Node: def __init__(self, val=None): self.left, self.right, self.val = None, None, val   def levelOrderPrint(tree): if not tree: return nodes=collections.deque([tree]) currentCount, nextCount = 1, 0 while len(nodes)!=0: currentNode=nodes.popleft() currentCount-=1 print currentNode.val, if currentNode.left: nodes.append(currentNode.left) nextCount+=1 if currentNode.right: nodes.append(currentNode.right) nextCount+=1 if currentCount==0: #finished printing current level print '\n', currentCount, nextCount = nextCount, currentCount```

The time complexity of this solution is O(N), which is the number of nodes in the tree, so it’s optimal. Because we should visit each node at least once. The space complexity depends on maximum size of the queue at any point, which is the most number of nodes at one level. The worst case occurs when the tree is a complete binary tree, which means each level is completely filled with maximum number of nodes possible. In this case, the most number of nodes appear at the last level, which is (N+1)/2 where N is the total number of nodes. So the space complexity is also O(N). Which is also optimal while using a queue.

This is one of the most common tree interview questions and everyone should know it off the top of their head.

VN:F [1.9.22_1171]
Programming Interview Questions 20: Tree Level Order Print, 8.1 out of 10 based on 20 ratings
This entry was posted in Programming Interview. Bookmark the permalink.

Here is a sample implementation in C++ with all the inlined comments:

#include
#include

struct BTNode {
int data;
BTNode *left;
BTNode *right;
};

void LevelPrintBT(BTNode *root)
{
BTNode *cur;
std::queue nodes;
int curcount = 0;
int nextcount = 0;

nodes.push(root);
curcount = 1;

while(!nodes.empty()) {
cur = nodes.front();
nodes.pop();
curcount -= 1; // Decrease the counter of current level nodes by one
printf(“%4d “, cur->data); // print the current node

/* Add the left node to the queue and increase the next level counter by one. */
if (cur->left) {
nodes.push(cur->left);
nextcount++;
}

/* Add the right node to the queue and increase the next level counter by one. */
if (cur->right) {
nodes.push(cur->right);
nextcount++;
}

/* If we have finished processing all the nodes in the current level
– set the current nodes counter to the next level nodes count;
– reset the next level counter;
*/
if (0 == curcount) {
curcount = nextcount;
nextcount = 0;
printf(“\n”); // print a newline to seperate the next level nodes
}
}
}

• Ramakrishnan

Is it not possible to use recursion for this ?

You can have a hash table that has the level as the ‘key’ and the array of nodes as the ‘value’. Re-curse down the tree in in-order mode (left child first, then right child), appending the node to the correct key of the hash table. The recursion can track the level as well, which will be the key of the hash table to append. After traversing the tree, we can traverse through the keys of the hash table and print the elements one after the other. Time complexity will be O(N) for traversing through tree and O(N) for printing the elements. Space complexity should be O(N) as well.

• Arden

Great solution, thanks a lot for pointing it out!

• Anonymous

Awesome Solution!

@Ramakrishnan
I did not quite understand your solution regarding the hash table(s), which one of
the below solutions are you suggesting?

1. Create a hash table for each level or;
2. Create a single hash table for all the tree, where as I presume each level
shall be an array (or a list) of nodes.

In case if you are suggesting Item #1 above, the solution will not work cause
the hash table will try to store more than one value for the same key starting
from level #1.

In case of solution #2, I agree that this is going to work, though it will
require O(N) space as you correctly noted.

Anyway, the #2 has some advantages listed below.
You can print the nodes of any required level in whatever order you like –
left-to-right or right-to-left, or alternate the order of printing between
levels, which will result in the BT being printed in a spiral (BTW, this was
one of the on-site interview questions recently held this April in Moscow by Microsoft).

For any subsequent queries on BT’s level, you can print it out instantly,
without traversing the BT again.

• Arden

I think he’s suggesting solution #2. Thanks for listing the advantages.

• rohit

great solution and great line”Understanding the code is easier than its explanation”.

• Jaime

Hi Arden,

Awesome post. Small observation: Don’t you have to append the nodes that you are popping in a string S and then, when you print the newline, print S as well (and assigning S = “” again) ? This way you will satisfy the initial requirement.

Thanks!

• Vamsi

This solution assumes that the tree is balanced and it does not work for a non balanced binary tree. One way I can think of solving it is using one more queue which tracks the level as well.

``` public static void print(BinaryTreeNode node) { if (node == null) return; Queue queue = new LinkedList(); Queue levelQueue = new LinkedList(); queue.add(node); levelQueue.add(0); int lastLevel = 0; while (queue.peek() != null) { BinaryTreeNode dequeuedNode = queue.poll(); Integer level = levelQueue.poll(); if (lastLevel != level) { System.out.println(); lastLevel = level; } System.out.print(dequeuedNode.data + " "); if (dequeuedNode.left != null) { queue.add(dequeuedNode.left); levelQueue.add(level + 1); } ```

``` if (dequeuedNode.right != null) { queue.add(dequeuedNode.right); levelQueue.add(level + 1); } } } ```

Java code:

static void PrintTree(Node root) {

if(root==null)

System.out.println(“Root is null”);

int currentLevel=1;

int nextLevel=0;

while(!q.isEmpty()) {

Node n= q.poll();

currentLevel–;

System.out.print(n.data);

if(n.left != null) {

nextLevel++;

}

if(n.right != null) {

nextLevel++;

}

if(currentLevel == 0) {

System.out.println();

currentLevel= nextLevel;

nextLevel=0;

}

}

}

• presman

I think there is a simpler solution – start with the root as the only element in ‘current’ stack. scan through all nodes in the stack. for each scanned node, record append left and right children to the ‘next stack’, don’t forget to print ‘current stack’ elements. Once done with the current stack, swap the stacks, and print new line. here’s the code:

def printlevel( root ):
stack0 = [ root ]
while stack0:
stack1 = []
for r in stack0:
print r._val,
if r._l:
stack1.append( r._l )
if r._r:
stack1.append( r._r )
print
stack0 = stack1[:]

• jairp

Yes, you are right. this is simpler approach without having to maintain two explicit counters.

• Neel Sheyal

We can print the binary tree with nodes in a new line for each level by using two queue. The first queue will hold the binary tree at each level and the second queue will hold the number of current level. After finishing the printing of the nodes in one level we are inserting the new line and increasing the number of level by 1. For explanation and code http://www.algoqueue.com/algoqueue/default/view/8519680/print-binary-tree-level-by-level

To print the binary tree level by level with new line http://www.algoqueue.com/algoqueue/default/view/8585216/print-binary-tree-level-by-level-with-new-line