Jonathan Swiecki Jonathan Swiecki - 2 months ago 32
C Question

Level-order traversal of a binary tree

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

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)
}