Convert recursion to an explicit stack
Updated
Replace call f(x) with stack.push(x) (or a frame with a phase). Replace return with pop and a loop. Preorder DFS: push children. The loop runs while the stack is nonempty. Base case is do not push.
What to focus on
If work happens after the recursive call, store a phase in the frame (enter vs exit) so you can resume. Tail recursion can reuse one frame. Do not assume that.
Worked examples
preorder
a = [4, 1, 9] as a chain 4→1→9- push 4, pop visit, push next
- like the call stack of rec(head.next)
Result: visits 4,1,9
with leftover
a = [4, 1, 9], visit after children- frame phases: enter, after-left, after-right
Result: phase on the pair
empty
a = []- do not push
- loop never runs
Result: no visit
Try it
Write walkList(a). a is a list of integers as a chain. Rewrite the recursive walk as while stack is nonempty. Push a frame before you visit it. For leftover work after children, store a phase. a = [4, 1, 9] as a chain 4→1→9 → visits 4,1,9. a = [4, 1, 9], visit after children → phase on the pair. a = [] → no visit.
The list may be empty. Values are integers. Push a frame before you visit it.