Good day,
Just to be clear: I am not looking for recursive or iterative solutions, Wikipedia has sufficient pseudocode to implement pre-, in- and post-order traversal of any tree.
I am interested in building a finite-state machine to traverse a binary tree.
A Tree consists of Nodes. Nodes have a LeftChild, a RightChild, and a Parent property.
The FSM halts at a Node at any given time, and can have as many states as required, but NO DYNAMIC STACK of any sort (which distinguishes it from a Turing machine). On input "GiveNext" the machine should halt on the next node (say traversing the tree in-order.)
I've tried for quite a while now, and suspect, that it is not possible, but I am not sure. The problem is the need to keep track of recent decisions, so that on revisiting a Node via Parent one can turn right when left has been processed.
Thoughts?
Thanks in advance! Herb