Breadth First Vs Depth First

Question

When Traversing a Tree/Graph what is the difference between Breadth First and Depth first? Any coding or pseudocode examples would be great.

Answer 1

These two terms differentiate between two different ways of walking a tree.

It is probably easiest just to exhibit the difference. Consider the tree:

    A
   / \
  B   C
 /   / \
D   E   F

A depth first traversal would visit the nodes in this order

A, B, D, C, E, F

Notice that you go all the way down one leg before moving on.

A breadth first traversal would visit the node in this order

A, B, C, D, E, F

Here we work all the way across each level before going down.

(Note that there is some ambiguity in the traversal orders, and I've cheated to maintain the "reading" order at each level of the tree. In either case I could get to B before or after C, and likewise I could get to E before or after F. This may or may not matter, depends on you application...)

---

Both kinds of traversal can be achieved with the pseudocode:

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

The difference between the two traversal orders lies in the choice of Container.

• For depth first use a stack. (The recursive implementation uses the call-stack...)
• For breadth-first use a queue.

---

The recursive implementation looks like

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

The recursion ends when you reach a node that has no children, so it is guaranteed to end for finite, acyclic graphs.

---

At this point, I've still cheated a little. With a little cleverness you can also work-on the nodes in this order:

D, B, E, F, C, A

which is a variation of depth-first, where I don't do the work at each node until I'm walking back up the tree. I have however visited the higher nodes on the way down to find their children.

This traversal is fairly natural in the recursive implementation (use the "Alternate time" line above instead of the first "Work" line), and not too hard if you use a explicit stack, but I'll leave it as an exercise.