Breadth-First Traversal

Data Structures and Algorithms with Object-Oriented Design Patterns in Java

Breadth-First Traversal

Program defines the breadthFirstTraversal method of the AbstractTree class. As defined in Section , a breadth-first traversal of a tree visits the nodes in the order of their depth in the tree and at each level the nodes are visited from left to right.

program15584
Program: AbstractTree class breadthFirstTraversal method.

We have already seen in Section a non-recursive breadth-first traversal algorithm for N-ary trees. This algorithm makes use of a queue as follows. Initially, the root node of the given tree is enqueued, provided it is not the empty tree. Then, the following steps are repeated until the queue is empty:

Remove the node at the head of the queue and call it head.
Visit the object contained in head.
Enqueue in order each non-empty subtree of head.

Notice that empty trees are never put into the queue. Furthermore, it should be obvious that each node of the tree is enqueued exactly once. Therefore, it is also dequeue exactly once. Consequently, the running time for the breadth-first traversal is