# Iterative Tree Traversal using a stack

• 03-09-2003
Iterative Tree Traversal using a stack
Hi guys,

In my final thoughts on my scheduling algo, I have elected to imitate a recursive call with a stack. Thanks for the advice Codeplug. The pseudo code for my algo is as follows:

Code:

```while(!empty())     peek at top item; // This involves scheduling it, etc     push() on next branches; // Put the next level of calls on stack         continue if there were pushes done     pop(); // Only do this if we didn't push anything on         this mimics the return of the recursive function call end while```
All is well, except for one thing: After going down, then coming back up, I'll peek at the same node more than once. I somehow need to skip it, or pop it off the 2nd time I see it. Picture this tree for example:

Code:

```            1     /      |    \     2      2      2   / | \  / | \  / | \   3 3 3  3 3 3  3 3 3```
My goal is to travers the tree in normal order:
1 to 2 via left branch
2 to 3 via left branch
2 to 3 via middle branch
2 to 3 via right branch
1 to 2 via middle branch
2 to 3 via left branch
etc.....

Using my algorithm, I "visit" a node, and do the scheduling, etc, at the beginning of my while loop when I peek at the top. Later, I pop it off to simulate the recursive call. Thus, for example, when I've gone down the left third of the tree, my stack looks like this:

Code:

```r m l r m l r m l   1  |  2  |  3```
Where r, m, l mean right, middle, left for the branches, and the numbers below are for what node we're talkinga about. After I've explored all three paths from 2 to 3, my stack will look like this:
Code:

```r m l r m l   1  |  2```
This is where I run into a problem. Based on my algo, I will now peek at 2's left path, and push from there. Well, I already did that! How do I indicate that I need to pop that item, and insted travers 2's middle path?

My code is below, if it's any help. Kind of messy right now, with lots of global data (used to make my previous recursive solution faster) Any ideas??????

Thanks!

Code:

```void solveIter () {     stack<StackStructType> callStack;     StackStructType current;     current.job = 0;     current.comp = '-';     callStack.push(current);     for (int i = Job::getMachPerJob() - 1; i >= 0 ; i--)     {         current.comp = jobs[current.job].getComp(i);          callStack.push(current);     }     while (!callStack.empty())     {         current = callStack.top();                 if (current.comp != '-' && !jobs[current.job].isScheduled())         {             numOfJobs++;             if (numOfJobs > currentBest)             {                 currentBest = numOfJobs;                 best = jobs;             }             computers[current.comp - 97].addJob(jobs[current.job].getEnd());             jobs[current.job].setSchedule(current.comp);         }         if (current.job + 1 < jobSize)         {             current.job += 1;             current.comp = '-';             callStack.push(current);             for (int i = Job::getMachPerJob() - 1; i >= 0; i--)             {                 if (computers[jobs[current.job].getComp(i) - 97].isAvailable(jobs[current.job].getStart()))                 {                     current.comp = jobs[current.job].getComp(i);                      callStack.push(current);                 }             }             continue;         }         current = callStack.top();         callStack.pop();         if (current.comp != '-')         {             numOfJobs--;             computers[current.comp - 97].removeJob();         }     } }```
• 03-10-2003
Codeplug
What about something like visited in the StackStructType?

gg
• 03-10-2003
I had something like that, only I had it as a member of the corresponding job object. This was causing me some problems, in that I would start scheduling jobs that I just popped, so I need to re work that part, I guess. I will try it, as you suggest, and put it into the stackType type. Just so I'm on the same page, when I peek, I should set it to true...
• 03-10-2003
Here is what I have now....

I still end up scheduling the same job over and over and getting in an infinite loop...

Any thoughts?

Code:

```void solveIter() {     stack<StackStructType> callStack;     StackStructType current;     int previousJob;     current.job = 0;     current.comp = '-';     current.visited = false;     callStack.push(current);     for (int i = Job::getMachPerJob() - 1; i >= 0 ; i--)     {         current.comp = jobs[current.job].getComp(i);          callStack.push(current);     }     while (!callStack.empty())     {         current = callStack.top();         callStack.pop();                 if (!current.visited)         {             if (current.comp != '-')             {                 numOfJobs++;                                 if (numOfJobs > currentBest)                 {                     currentBest = numOfJobs;                     best = jobs;                 }                 computers[current.comp - 97].addJob(jobs[current.job].getEnd());                 jobs[current.job].setSchedule(current.comp);                 current.visited = true;                 callStack.push(current);             }             if (current.job + 1 < jobSize)             {                 current.job += 1;                 current.comp = '-';                 callStack.push(current);                                 for (int i = Job::getMachPerJob() - 1; i >= 0; i--)                 {                     if (computers[jobs[current.job].getComp(i) - 97].isAvailable(jobs[current.job].getStart()))                     {                         current.comp = jobs[current.job].getComp(i);                          callStack.push(current);                                             }                 }                 continue;             }         }         current = callStack.top();         callStack.pop();         cout << "Returning from " << current.job << "," << current.comp << endl;         if (current.comp != '-')         {             numOfJobs--;             computers[current.comp - 97].removeJob();                    }     } }```
• 03-10-2003
Codeplug
I'm gonna have to go back to the original recursive solution and think about coverting it - (I'm too lazy to digest the code you've already done :) )

gg
• 03-10-2003
Codeplug
Ok, the original recursive algorithm (that works):
Code:

```void solveRecurse(int currentJob) { 1    char currentJobSched = jobs[currentJob].getSchedule(); 2    int jobSize = jobs.size(); 3    char getComp; 4 5    if (currentJobSched != '-' && currentJob >= 0) 6    { 7        numOfJobs++;        8        if (numOfJobs > currentBest) 9        { 10            currentBest = numOfJobs; 11            best = jobs; 12        } 13        computers[currentJobSched - 97].addJob(jobs[c4urrentJob].getEnd());        14    } 15    if (currentJob + 1 < jobSize) 16    { 17        for (int i = 0; i < Job::getMachPerJob(); i++) 18        {            19            getComp = jobs[currentJob + 1].getComp(i); 20            if (computers[getComp - 97].isAvailable(jobs[currentJob + 1].getStart())) 21            { 22                jobs[currentJob + 1].setSchedule(getComp); 23                solveRecurse(currentJob + 1); 24            } 25        } 26        jobs[currentJob + 1].setSchedule('-'); 27        solveRecurse(currentJob + 1); 28    }    29    if (currentJobSched != '-' && currentJob >= 0) 30    { 31        computers[currentJobSched - 97].removeJob(); 32        numOfJobs--; 33    }    }```
And here is the speudo code for an iterative implementation of a tail-recursive algorithm:
Code:

```//prime the pump push initial locals WHILE stack not empty   //this is our "recursive" entry point, peek the TOS to get locals   ...   //to mimic a recursive call, push and continue   ...   //to mimic a "return", pop and continue ENDWHILE```
The problem is that the recursive algorithm is not tail recursive. Namely, both recursive calls on lines 23 and 27 both need to do additional work when the recursive calls return.
So my idea is to expand the functionality at the top of the WHILE to being not only the recursive entry point, but also the "do post recursive call work".

To accoplish this, each stack frame will also keep up with the following state information:
- in recursion site 1 call (line 23)
- in recursion site 2 call (line 27)
Then, to mimic a recusive call on lines 23 and 27 you will:
Code:

```  set state in current frame (TOS), "in recursion site [1,2] call"   push frame for new recursive call   continue```
The WHILE loop will then look something like:
Code:

```WHILE stack not empty   peek TOS to get current frame   IF in recursion site 1 call       do work that follows site 1 call   ELSE IF in recursion site 2 call       do work that follows site 2 call   ELSE       do work for a "fresh" call   ENDIF ENDWHILE```
As is, this will have a LOT of redundant code since "work after site 1" includes "work after site 2", and the final ELSE contains all that work.........if there were ever a reason to use goto's THIS IS IT! Its a rare opportunity indeed, lets relish it :)
So we can keep the original form and just place some labels right after the "continue" that represents the recursive call mimic for lines 23 and 27. The WHILE loop then looks like:
Code:

```WHILE stack not empty   peek TOS to get current frame   IF in recursion site 1 call       goto post_site_1_call   ELSE IF in recursion site 2 call       goto post_site_2_call   ENDIF   do work for a "fresh" call ENDWHILE```
What do you think?

gg
• 03-10-2003