Jonathan Swiecki - 9 months ago 106

C 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

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

Source (Stackoverflow)