Level-order traversal of a binary tree

Question

I want to perform level-order traversal of a binary tree. Hence, for a given tree, say:

     3
    / \
   2   1
  / \   \
 4   6   10

the output would be:

3 2 1 4 6 10

I understand that I could use some sort of queue, but what is the algorithm to do this in C recursively? Any help appreciated.

Answer 1

The graph algorithm is called Breadth First Search, it uses a queue to perform the level-order traversal, here is the pseudo-code

void breadth_first(Node root)
{
  Queue q;
  q.push(root);
  breadth_first_recursive(q)
}

void breadth_first_recursive(Queue q)
{
  if q.empty() return;
  Node node = q.pop()
  print Node
  if (n.left) q.push(n.left)
  if (n.right) q.push(n.right)
  breadth_first_recursive(q)
}