The "left-hand-rule maze traversal" requires backing out of dead ends (in a tree data structure, up from leaf nodes), which amounts to one permanent parent pointer per node instead of a transient stack of nodes that we have not finished visiting (in addition to the baseline of child pointers).
For what it's worth, repeatedly traversing from the root _doesn't_ require backing out of dead ends, if you can avoid traversing into dead ends. Specifically if you store the size of the subtree at the node you can traverse directly to the ith element from the root, and do that N times and you get a traversal.
That constant space used to store the size could instead be a pointer to the root, but all the use cases I have for trees involve aliasing subtrees in which case there can be multiple "parents" for a given subtree and one cannot point to it.
In the spirit of completeness, my standard tree traversal recurses to a fixed depth and then falls back to the walk-repeatedly-from-the-root, which is constant space of a sort, but feels suboptimal.
Space proportional to node count (used for a pointer or a tree size or something fancier) is up to exponentially larger than space proportional to tree depth (for a stack representing the state of a traversal), the same if every node has only one child.
It might be a competitive approach if the tree is very unbalanced or there are enough concurrent traversals, but in main experience the main reason to use parent pointers or the like are operations that are not visiting each node once starting from the root.
