binary tree -print the elements according to the level

Question

This question was asked to me in an interview:

lets say we have above binary tree,how can i produce an output like below

2 7 5 2 6 9 5 11 4

i answered like may be we can have a level count variable and print all the elements sequentially by checking the level count variable of each node. probably i was wrong.

can anybody give anyidea as to how we can achieve that?

Answer 1

You need to do a breadth first traversal of the tree. Here it is described as follows:

Breadth-first traversal: Depth-first is not the only way to go through the elements of a tree. Another way is to go through them level-by-level.

For example, each element exists at a certain level (or depth) in the tree:

    tree
      ----
       j         <-- level 0
     /   \
    f      k     <-- level 1
  /   \      \
 a     h      z  <-- level 2
  \
   d             <-- level 3

people like to number things starting with 0.)

So, if we want to visit the elements level-by-level (and left-to-right, as usual), we would start at level 0 with j, then go to level 1 for f and k, then go to level 2 for a, h and z, and finally go to level 3 for d.

This level-by-level traversal is called a breadth-first traversal because we explore the breadth, i.e., full width of the tree at a given level, before going deeper.