Yes, sure, there's an isomorphism. Using that fact, is it then so trivial to show how this FSM approach works out if you don't have a binary tree to start with? I think it would make an interesting follow-up blog post. But failing that, it would have been nice to call out at the top that these are binary trees.
It definitely doesn't work if you don't change your in-memory data representation, and it requires you to change it in a way that forecloses the possibility of FP-persistent tree structures or efficient DAGs. Compared to that, representing your ordered-tree nodes as cons chains is a barely-significant change.
It does generalize, though, to ordered-tree nodes that aren't represented as cons chains. You just have to walk through the n child pointers when you're moving back up the tree to search for the one you're returning from, adding an extra runtime cost factor proportional to n but no extra memory. Moreover, if you devote three or four registers to an amnesic stack, you can avoid that cost for the bottom two or three levels of the tree, which will necessarily contain the vast majority of tree nodes.
