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.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: