Jonathan Swiecki Jonathan Swiecki - 9 months ago 106
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:

/ \
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.


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;

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)