It seems like by adding parent pointer one is shifting complexity from the traversal into the data structure, in order to avoid a stack. I know there are places where avoiding an explicit stack can be nice (perhaps a BVH tree in a shader or other places where constant space is required?) but are there more good reasons for it?
A DAG (such as a singly linked tree) has so many benefits for memory safety, GC performance, ability to extend it from a binary tree to N children etc., that it seems like an odd tradeoff in most scenarios.
Obviously, adding read-only data in the tree and to save mutable data in the traversal state can be amortized if we have many ongoing traversals rather than one. For example, in a massively parallel GPU computation running an arbitrary number of tree searches simultaneously in a fixed memory amount.
