Posts Tagged Tree Traversal

Print a tree level by level (Level Order Traversal)

Printing a tree level by level

A common interview question in which you would be asked to write a code that would print a binary tree by level. For example the below binary tree when passed to your code should print 7,6,11,3,5,13,12



 

 

 

 

 

This is also known as level order traversal. The level order traversal of a tree is also breadth first traversal of the tree. The concept of level order traversal is to visit the root and then visit all nodes 1 level away, then all nodes 2 levels away and so on. We would need a queue to perform this kind of traversal.

The psuedocode for the program would be as follows:

Create an empty queue “Q”
enqueue the root element of the tree
while queue is NOT empty
dequeue an element from the queue
print element
Get children of the dequeued element
enqueue children

Having written the psuedocode its now very straight forward to convert this into a working C++ code.

 

 

Leave a Comment