# My first question.

• 12-03-2011
hawkfan50
My first question.
So the question is

Write an Iterator that will perform a depth first search on any N-ary Tree.

We just started reading about trees so I'm not overly familiar with them. I understand the basic concepts of them. So my question is, does this require writing an iterator class or is it possible to do with a single algorithm? I found this online:

Code:

``` public void DfsIterative(Node node) {        var trail = new Stack<Transition>();        DoSomethingWithNode(node);        PushAllTransitionsToStack(node, trail);        while(trail.Count>0) {        Transition t = trail.Pop();        Node destination = t.Destination;        DoSomethingWithNode(destination);        PushAllTransitionsToStack(destination, trail);          }        }```

This is labeled as classical iterative version of DFS. I don't understand how that iterates.
• 12-03-2011
bernt
Trees lend themselves very well to recursion. The two are often taught together in class (read: you're going to be studying recursion soon if you haven't already).

With that in mind, the code you posted is iterative in the sense that it doesn't technically recurse. It's basically the same algorithm though, see this for comparison. The only difference is that instead of using the run-time stack (eg, calling the function recursively), it's using its own stack, and pushing/popping at appropriate times. There's usually a performance increase associated with avoiding the run-time stack (in case you're wondering why anyone would bother with the "iterative" version).