How do you rewrite a recursive tree walk as a Python `while` loop over an explicit stack?

### The transformation A recursive walk over a nested structure keeps its pending work in frames: each call holds one node plus whatever parameters it was given, and the interpreter remembers where to resume. Because CPython never reuses a frame, the only way to walk an arbitrarily deep structure is to move that pending work off the call stack and into a container you control. The shape is always the same: ```python stack = [root] while stack: node = stack.pop() visit(node) stack.extend(children_of(node)) ``` Three things are worth naming in that snippet. `while stack:` tests the list for emptiness through its truthiness — an empty list is falsy — which is the idiomatic spelling and does the same job as the recursion's "no more branches to descend". `stack.pop()` removes and returns the last element, which is amortized O(1) because nothing after it has to move. `stack.extend(...)` pushes all the children in one call, which is both faster and clearer than a loop of `append`. ### What has to go on the stack The frames were not holding only the node. Every parameter the recursive call passed — a depth counter, an accumulated path, a parent reference, a flag saying whether you are inside an already-matched subtree — lived in a frame too, and after the rewrite it has to live in the stack entry. Push a tuple and unpack it on pop: ```python stack = [(root, 0, ())] while stack: node, depth, path = stack.pop() ... stack.extend((child, depth + 1, path + (node,)) for child in children_of(node)) ``` The rule of thumb is exact: the explicit stack must hold everything a frame held. Anything you forget to push is state the loop cannot recover, and it usually shows up later as a subtly wrong result rather than an error. ### list or collections.deque Use a plain `list` for a stack. `list.append()` and `list.pop()` both operate at the end of the list and are amortized O(1); the list over-allocates so appends rarely copy, and popping from the end moves nothing. Reach for `collections.deque` when you take items from the *front*. `list.pop(0)` has to shift every remaining element left by one, so a first-in-first-out walk built on a list degrades to quadratic time on a wide structure — a real and easily-missed performance bug. `collections.deque` is a doubly linked list of blocks with O(1) `append`, `pop`, `appendleft` and `popleft`, so a queue built on it stays linear. A deque also accepts a `maxlen`, which silently discards from the other end when full — handy for a bounded buffer, wrong for a work queue, so do not set it here by accident. For a stack specifically, a deque is not faster than a list, and it is one more import; pick the container by which end you take from, not by reputation. ### Termination and cycles The recursion stopped at its base case, once per branch. The loop stops on one condition — the container is empty — which is the same statement made once instead of once per path. Neither version protects you from a cycle: if the data can point back at an ancestor, the recursion recurses forever and the loop loops forever, and the loop is arguably worse because it will happily consume memory until the process dies rather than tripping the interpreter's nesting guard. Keep a `set` of visited keys and check it before pushing, whenever the structure is data you did not construct yourself. ### What you gain and what you pay You gain unbounded depth: the stack list lives on the heap, so it is limited by memory rather than by the interpreter's nesting limit, and it can hold millions of entries. You also gain speed, because a loop iteration is far cheaper than a function call, and you gain the ability to pause, checkpoint or resume the walk — the work queue is an ordinary object you can inspect, serialize or hand to something else. You pay in readability. The recursive version reads like the definition of the structure; the loop version reads like a machine. You also pay in diagnostics: the frames used to record where you were, and after the rewrite every iteration runs on the same source lines, so you have to put the identifying context into the stack entries and into whatever you log or raise. ### The interview answer Seed a container with the root, loop while it is non-empty, pop, do the node's work, push the children along with every parameter the recursion carried. Use a list when you take from the end, a `collections.deque` when you take from the front, and never `list.pop(0)` for a queue.