Re:Tree traversal without recursion: the tree as a state mac...
by normalhuman on Tuesday September 03, 2019 @03:31AM
(#20864347)
> How can it be a state machine if you aren't mutating it?
You are confusing a state machine (which is an abstract model of computation) with the behavior of a program implementing it. The set of possible states and the conditions of transition from one state to the next never change.
These conditions can depend on mutable state, as is the case described by the author (in this case, mutable state is kept in the current and previous node pointers).
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.