Breadth-first Traversal

In breadth-first traversal (also called level-order traversal or generational traversal), we traverse the tree generation by generation, from left to right. For example, for the binary tree below, we start at the first generation, which has only one node, the root n(a).

Then we start at the next generation, visiting from the left:

to the right:

Hence, for generational traversal, we have the traversal sequence (na,nb,nc).{(n_a, n_b, n_c).} For a left-skewed tree, we have the traversal sequence (na,nb).{(n_a, n_b).}

And for a right-skewed tree, we have the traversal sequence (na,nc).{(n_a, n_c).}

Implementation

Consider the following tree (edge labels are pointer values):

In level-order traversal, we traverse the tree's nodes level by level. Thus, for the tree above, we have the traversal:

⟨8,3,9,7,6,4,5,2⟩\lang 8, 3, 9, 7, 6, 4, 5, 2 \rang

As with the other traversal methods, we can implement level-order traversal the tree by making use of queue.

fn levelOrder(Node* root) -> void:
	Queue qeueue = newQueue();
	print((*root).data)
	enqueue(qeueue, root);
	while (!isEmpty(q)):
		root = dequeue(qeueue);
		if ((*root).leftChild):
			print((*(*root).leftChild).data);
			enqueue(queue, (*root).leftChild);
		if ((*root).rightChild):
			print((*(*root).rightChild).data);
			enqueue(queue, (*root).rightChild);

Here's a line by line summary of the code above:

  1. Declare the function.
  2. Create a new empty queue.
  3. Print the root's data. This is the first node in the tree, the root node.
  4. Enqueue root to the queue.
  5. As long as the queue is not empty, execute the following instructions. If the queue is empty, END.
  6. Dequeue the queue, and make root the dequeued value (a node).
  7. If the dequeued node has a left child, execute the instructions below. Otherwise, go to instruction 9.
  8. Print the dequeued node's data.
  9. Enqueue the left child of the dequeued node to the queue.
  10. If the dequeued node has a right child, execute the instructions below. Otherwise, go back to instruction 4.
  11. Print the dequeued node's data. Enqueue the right child of the dequeued node to the queue.