Thread: My first question.

  1. #1
    Registered User
    Join Date
    Dec 2011

    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:

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

    This is labeled as classical iterative version of DFS. I don't understand how that iterates.

  2. #2
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    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).
    Consider this post signed

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 03-23-2011, 09:00 AM
  2. *szString = things question/memory question
    By Jang in forum C Programming
    Replies: 3
    Last Post: 01-20-2011, 04:59 AM
  3. Newbish Question file reading question....
    By kas2002 in forum C Programming
    Replies: 23
    Last Post: 05-17-2007, 12:06 PM
  4. Self regiserting DLLs question and libraries question.
    By ApocalypticTime in forum Windows Programming
    Replies: 2
    Last Post: 03-22-2003, 02:02 PM
  5. A question of color...(not a racial question)
    By Sebastiani in forum Windows Programming
    Replies: 7
    Last Post: 01-15-2003, 08:05 PM