 By Amin Ariana — October 2001

Write an algorithm that takes a tree data structure and writes out all the elements in a breadth-first traversal order.

## Problem Statement

Write pseudo-code that takes a tree data structure and writes out all the elements in a breadth-first traversal order.

## Evaluation

• Completeness of pseudo-code algorithm (25%)

• Correctness of the algorithm, demonstrated by quick manual unit tests (25%)

• What is the time and space complexity in the average and worst cases? (25%)

• Change your code to also print a new-line after each level of the tree is written out (25%)

## Solution

C# solution courtesy of Paul Hounshell :

```// Done as an iterative coroutine; it's more useful
Queue<Node> queue = new Queue<>();
while (!queue.isEmpty()) {
Node next = queue.dequeue();
if (next.left != null) queue.enqueue(next.left);
if (next.right != null) queue.enqueue(next.right);
yield return next;
}
}
```

Paul's response to part (d) : change ...

```Queue<Node>
```

to:

```Queue<Pair<Node, int>>
```

where the int is a level. Simple after that.

## References

One of my second year course assignments in University of Waterloo