> You can get rid of any stacks whatsoever by keeping a parent pointer in the tree node data structure. Effectively, this turns the tree into a (sort of) state machine.

How can it be a state machine if you aren't mutating it?

In fact, you can traverse a tree without recursion (or any equivalent stack-like structure) and without parent pointers. And then you actually use the tree as a state machine: you stash the reverse path pointer in the tree itself by overwriting the downward links temporarily and then putting them back.

This is useful for garbage collection; you can have a garbage collector that is guaranteed never to blow the stack in the marking phase.