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

Recommended reading

Author
Amin Ariana
Published
October 2001