Suppose you have just one function being called recursively. (2-function scenario is similar.) Say it has 5 parameters. Create a struct named FRAME (having 5 fields + possibly a field for lineNo/instructionPointer.)
Maintain a stack holding the Frame instances. Each time the recursive algorithm adds to the call stack, we add to our stack too.
Wiki page on inorder tree walk has very concise recursive/iterative algos. https://github.com/tiger40490/repo1/blob/py1/py/tree/iterative_InOrderWalk.py is my own attempt that’s not so simple. Some lessons:
- Differentiate between popping vs peeking the top.
- For a given node, popping and printing generally happen at different times without any clear pattern.
- the sequence of pop() is probably a pre-order tree walk
- the sequence of print is an in-order tree walk
Advertisements
