Breadth First

A BreadthFirst traversal of this tree:

        A
     B     C
    D E   F G

visits the nodes in this order: A B C D E F G

See DepthFirst for another common way to traverse trees.

---

A breadth first traversal usually employs a queue of known but not yet visited nodes.

  void visit (Queue q) {
    q.add(left);
    q.add(right);
  }

Useful work can be done anywhere in the method with little effect on the traversal. Conditional logic is avoided by making empty trees be NullObjects that implement visit() but do nothing. A non-recursive loop drives this traversal by seeding the queue with the root and looping until the queue is exhausted.

  Queue q = new Queue (root);
  while (!q.empty()) {
    q.remove().visit(q);
  }

The queue can grow to be quite large (as large as the "next" level of the tree). If this isn't acceptable, you can fake BreadthFirst search with IterativeDeepening?: search (DepthFirst) to depth 1, then to depth 2, then to depth 3, and so on. At each stage, you can ignore all but the maximum-depth nodes if you like. This takes more time and less space; it's more attractive for trees with a higher branching factor.