Breadth First Tree Traversal
Write an algorithm that takes a tree data structure and writes out all the elements in a breadthfirst traversal order.
Problem Statement
Write pseudocode that takes a tree data structure and writes out all the elements in a breadthfirst traversal order.
Evaluation
 Completeness of pseudocode 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 newline 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
public Iterable<Node> breadthFirst(Node node) {
Queue<Node> queue = new Queue<>();
queue.add(node);
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
Recommended reading

Calculate your Social Graph Klout Score
Write the algorithm that LinkedIn.com uses to tell you how many professionals you have access to.

Tree InOrder Traversal to Next Node
Given a node in a binary tree, implement the algorithm for finding its next inorder node in the containing tree.

Given a tree, prune it to select for only a certain node color
Given that a tree is made of only red or black nodes, return another tree that only has the paths of the original tree leading to a red node.

Closest Common Ancestor of a Node in a Tree
You have a tree data structure. Write an algorithm that given any two nodes in the tree, finds the node that is the closest common ancestor to them.
 Author
 Amin Ariana
 Published
 October 2001