440 Write a routine to list out the nodes of a binary tree i

4.40 Write a routine to list out the nodes of a binary tree in level-order. List the root, then nodes at depth 1, followed by nodes at depth 2, and so on. You must do this in linear time. Prove your time bound.

Solution

For every node visit the first node first and then in FIFO queue child nodes are kept.

PrintLevelOrder(tree)

1) Create an empty queue q

2) temp_node = root /*start from root*/

3) Loop while temp_node is not NULL

a) print temp_node --> data

b) Enqueue temp_node\'s children (first left then right child) to q

c) Dequeue a node from q and assign its value to temp_node

Time complexity ---- O(n) where n is the number of nodes in binary tree.