StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>These two terms differentiate between two different ways of walking a tree.</p> <p>It is probably easiest just to exhibit the difference. Consider the tree:</p> <pre><code> A / \ B C / / \ D E F </code></pre> <p>A <strong>depth</strong> first traversal would visit the nodes in this order</p> <pre><code>A, B, D, C, E, F </code></pre> <p>Notice that you go all the way <strong>down</strong> one leg before moving on.</p> <p>A <strong>breadth</strong> first traversal would visit the node in this order</p> <pre><code>A, B, C, D, E, F </code></pre> <p>Here we work all the way <strong>across</strong> each level before going down.</p> <p>(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...)</p> <hr> <p>Both kinds of traversal can be achieved with the pseudocode:</p> <pre><code>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 </code></pre> <p>The difference between the two traversal orders lies in the choice of <code>Container</code>. </p> <ul> <li>For <strong>depth first</strong> use a stack. (The recursive implementation uses the call-stack...)</li> <li>For <strong>breadth-first</strong> use a queue.</li> </ul> <hr> <p>The recursive implementation looks like</p> <pre><code>ProcessNode(Node) Work on the payload Node Foreach child of Node ProcessNode(child) /* Alternate time to work on the payload Node (see below) */ </code></pre> <p>The recursion ends when you reach a node that has no children, so it is guaranteed to end for finite, acyclic graphs.</p> <hr> <p>At this point, I've still cheated a little. With a little cleverness you can also <em>work-on</em> the nodes in this order:</p> <pre><code>D, B, E, F, C, A </code></pre> <p>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 <em>visited</em> the higher nodes on the way down to find their children.</p> <p>This traversal is fairly natural in the recursive implementation (use the "Alternate time" line above instead of the first "Work" line), and not <em>too</em> hard if you use a explicit stack, but I'll leave it as an exercise.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload