Illustration

Breadth First Tree Traversal

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

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

Amin A.

Written by

Amin Ariana

A software entrepreneur from San Francisco