Breadth-First Traversal of a Tree


  1. Helper data structure:

    Certain programming problems are easier to solve using multiple data structures.

    For example, testing a sequence of characters to determine if it is a palindrome (i.e., reads the same forward and backward, like "radar") can be accomplished easily with one stack and one queue. The solution is to enter the sequence of characters into both data structures, then remove a letter from each data structure one at a time and compare them, making sure that they are the same.

    In this palindrome example, the user (person writing the main program) has access to both data structures to solve the problem. Another way that 2 data structures can be used in concert is to use one data structure to help implement another.

    We will examine how a common data structure can be used to help traverse a tree in breadth-first order.

  2. Depth-first traversal:

    We have already seen a few ways to traverse the elements of a tree. For example, given the following tree:

          tree
          ----
           j    <-- root
         /   \
        f      k
      /   \      \
     a     h      z
      \
       d
    

    A preorder traversal would visit the elements in the order: j, f, a, d, h, k, z.

    This type of traversal is called a depth-first traversal. Why? Because it tries to go deeper in the tree before exploring siblings. For example, the traversal visits all the descendants of f (i.e., keeps going deeper) before visiting f's sibling k (and any of k's descendants).

    As we've seen, this kind of traversal can be achieved by a simple recursive algorithm:

    PREORDER-TRAVERSE(tree)
    
    if (tree not empty)
      visit root of tree
      PREORDER-TRAVERSE(left subtree)
      PREORDER-TRAVERSE(right subtree)
    

    The 2 other traversal orders we know are inorder and postorder. An inorder traversal would give us: a, d, f, h, j, k, z.

    Well, inorder and postorder traversals, like a preorder traversal, also try to go deeper first...

    For example, the inorder traversal visits a and d before it explores a's sibling h. Likewise, it visits all of j's left subtree (i.e., "a, d, f, h") before exploring j's right subtree (i.e., "k, z").

  3. Breadth-first traversal:

    Depth-first is not the only way to go through the elements of a tree. Another way is to go through them level-by-level.

    For example, each element exists at a certain level (or depth) in the tree:

          tree
          ----
           j         <-- level 0
         /   \
        f      k     <-- level 1
      /   \      \
     a     h      z  <-- level 2
      \
       d             <-- level 3
    

    (Computer people like to number things starting with 0.)

    So, if we want to visit the elements level-by-level (and left-to-right, as usual), we would start at level 0 with j, then go to level 1 for f and k, then go to level 2 for a, h and z, and finally go to level 3 for d.

    This level-by-level traversal is called a breadth-first traversal because we explore the breadth, i.e., full width of the tree at a given level, before going deeper.

    Now, how might we traverse a tree breadth-first? We'll need some other mechanism than the ones we've already used since preorder, inorder and postorder traversals don't produce breadth-first order.

  4. Why breadth-first:

    You may be thinking: "Why would we ever want to traverse a tree breadth-first?" Well, there are many reasons....

    Tree of Officers

    Suppose you have a tree representing some command structure:
                   Captain Picard
                 /                \
        Commander Riker       Commander Data
          /         \               |
     Lt. Cmdr.   Lt. Cmdr.      Lt. Cmdr.
     Worf        LaForge        Crusher
         |                          |
    Lieutenant                  Lieutenant
    Cameo-Appearance            Selar
    

    This tree is meant to represent who is in charge of lower-ranking officers. For example, Commander Riker is directly responsible for Worf and LaForge. People of the same rank are at the same level in the tree. However, to distinguish between people of the same rank, those with more experience are on the left and those with less on the right (i.e., experience decreases from left to right).

    Suppose a fierce battle with an enemy ensues. If officers start dropping like flies, we need to know who is the next person to take over command. One way to trace the path that command will follow is to list the officers in the tree in breadth-first order. This would give:

    1. Captain Picard
    2. Commander Riker
    3. Commander Data
    4. Lt. Cmdr. Worf
    5. Lt. Cmdr. LaForge
    6. Lt. Cmdr. Crusher
    7. Lieutenant Cameo-Appearance
    8. Lieutenant Selar

    Game Tree

    Another time when breadth-first traversal comes in handy is with game trees. Suppose we have a tree for a game of chess. In other words, levels of the tree alternately represent possible moves by you, and then by your opponent, and then by you...
                   current state of game
            /                |             \
       move                move     ...   move    <-- your moves
       queen's             king's         queen
       bishop              knight
     /     |    \         /    |   \        |
    move  move   ...   move  move  ...     ...    <-- opponent's moves
    king  queen's      king  king's
          rook               knight
            |                  |
            .                  .
            .                  .
            .                  .
    

    You have exactly 1 minute to decide on a move. Now, which would be a better use of that time: exploring the branch where you "move your queen's bishop" to its fullest extent (go deep) or explore each of your possible next move first, and then your opponent's responses (breadth-first).

    In this case, traversing the game tree breadth-first makes more sense than exploring one move infinitely (depth-first) before exploring another move.

  5. Help for breadth-first traversing:

    Let's return to example trees that are binary and that just hold characters.

    As we've seen, the recursive tree traversals go deeper in the tree first. Instead, if we are going to implement a breadth-first traversal of a tree, we'll need some help....Perhaps one of the data structures we already know can be of assistance?

    How to use helper data structure: What we'll do is store each element in the tree in a data structure and process (or visit) them as we remove them from the data structure.

    We can best determine what data structure we need by looking at an example:

       f
     /   \
    a     h
     \
      d
    

    When we are at element f, that is the only time we have access to its 2 immediate children, a and h. So, when we are at f, we'd better put its children in the data structure. Obviously then, f must have been in the data structure before them (i.e., first), since we'd have put f in when we were at f's parent.

    So, if we put the parent in the data structure before its children, what data structure will give us the order we need? In other words, to explore the tree breadth-first, do we want the children to be removed from the data structure first or the parent to be removed first?

    Answer: A queue will give us the order we want! A queue enforces first-in-first-out order, and we want to process the first thing in the data structure, the parent, before the later things in, its descendents.

  6. Using one data structure to implement another:

    The organization of a program that uses a breadth-first traversal might look like:

    main program        tree.h              tree.cpp
    ------------        ------              --------
    
    instantiate         class definition    Method definitions
    tree objects
    

    The main program needs to call some method that performs a breadth-first traversal, like Tree::breadthFirst(). This means that the interface (tree.h) must provide a prototype for such a method. Also, the implementation (tree.cpp), which the main program has no direct access to, must define the method Tree::breadthFirst().

    If we use a queue to help us implement the breadth-first traversal, then we must extend the picture...

    ...  tree.cpp               queue.h       queue.cpp
         --------               -------       ---------
    
    ...  Tree::breadthFirst()   queue         queue
         definition (uses       class         method
         a queue)               definition    definitions
    

    The tree implementation will use types and methods from the queue interface. The queue implementation will provide definitions for those methods, but they are hidden from the user of the queue--here, the user of the queue is the tree implementation.

  7. breadthFirst():

    Finally, we can implement the method Tree::breadthFirst(), which traverses a tree using a queue to achieve breadth-first order. Right now, we don't care what it does when its visits an element.

    This method just works on the entire tree and doesn't need to return anything, so its prototype in the class definition looks like:

    void breadthFirst();
    

    Now, the essence of the algorithm is to use a queue, in other words, to process nodes while there are node pointers left in the queue still to be processed.

    So, the core of the method will be looping through the contents of the queue:

    while (!queue.isEmpty()) {
      ...
    

    However, pointers to all the nodes in the tree won't be in the queue at once. We'll have to place them in the queue when we have access to them (i.e., we only get access to a child when we are at its parent).

    Here's one solution to the problem:

    void Tree::breadthFirst()
    {
      /* Temporary queue. */
      Queue queue;
      Tree *traverse;
    
      /*
       * Gotta put something in the queue initially,
       * so that we enter the body of the loop.
       */
    
      queue.insert(root);
    
      while (!queue.isEmpty()) {
        traverse = queue.remove();
    
        Visit the node pointed to by traverse.
    
        /*
         * If there is a left child, add it
         * for later processing.
         */
        if (traverse->getLeftSubTree() != NULL)
          queue.insert(traverse->getLeftSubTree());
    
        /*
         * If there is a right child, add it
         * for later processing.
         */
        if (traverse->getRightSubTree() != NULL)
          queue.insert(traverse->getRightSubTree());
      }
    
    }
    

  8. Using a stack instead:

    Suppose we replaced the use of a queue with a stack...

    void Tree::DifferentTraversal()
    {
      /* Temporary stack. */
      Stack stack;
      Tree *traverse;
    
      /*
       * Gotta put something in the stack initially,
       * so that we enter the body of the loop.
       */
      stack.push(root);
    
      while (!stack.isEmpty()) {
        traverse = stack.pop();
    
        Visit the node pointed to by traverse.
    
        /*
         * If there is a left child, add it
         * for later processing.
         */
        if (traverse->getLeftSubTree() != NULL)
          stack.push(traverse->getLeftSubTree());
    
        /*
         * If there is a right child, add it
         * for later processing.
         */
        if (traverse->getRightSubTree() != NULL)
          stack.push(traverse->getRightSubTree());
      }
    
    }
    

    What kind of traversal does this new method produce?

    Answer: A preorder traversal! However, it gives us right-to-left order, since the right child will come out of the stack before the left child.


    Why does a stack (using iteration) give us a preorder traversal? Well, suppose we had a recursive function traverse(), which performed a preorder traversal. Suppose you used this recursive function on the following tree:
          tree
          ----
           j
         /   \
        f      k
      /   \      \
     a     h      z
      \
       d
    

    Within each call of traverse() on a particular element (or whatever an element is held in, e.g., a node, an array element, etc.), there would be recursive calls to traverse its children. (Below indentation indicates another level of recursion.)

    traverse(j)
      traverse(f)
        traverse(a)
          traverse(d)
        traverse(h)
    

    Each of these recursive calls is a function call. When you call a function (or method), the parameter(s) of the function actually get pushed onto something called the call stack.

    So, the sequence of recursive calls above has the following effect on the call stack:

                             j
    call                ----------
    traverse(j)         call stack
    
                             f
                             j
    call                ----------
    traverse(f)         call stack
    
    
                             a
                             f
                             j
    call                ----------
    traverse(a)         call stack
    
    
                             d
                             a
                             f
                             j
    call                ----------
    traverse(d)         call stack
    
    
                             a
                             f
                             j
    return from         ----------
    traverse(d)         call stack
    
                             f
                             j
    return from         ----------
    traverse(a)         call stack
    
    
                             h
                             f
                             j
    call                ----------
    traverse(h)         call stack
    
    ...
    

    When the function is called, its parameter(s) go on the top of the call stack, and when the function returns, its parameter(s) get popped off of the call stack.

    In other words, with recursive traversal function (or methods), there is really a stack helping with the traversal.


BU CAS CS - Breadth-First Traversal of a Tree
This page created by Jisook Youn <jisook@cs.bu.edu>.
Material adapted for C++ from Breadth-First Traversal of a Tree (C version by Robert I. Pitts <rip@bu.edu>).