> Or for a possibly more useful comment, constant space tree traversal is genuinely quite difficult to implement. I don't know a general solution to it (other than walk from the start N times, quadratic style), would be interested to hear of one.

There's Morris tree traversal. It basically turns an ordinary binary tree into a threaded binary tree and fixes it up after it's done. But, this is mainly possible because of the space wasted by the null pointers at the leaves of the tree. You can hide a stack within the tree.

Constant space tree traversal is impossible and unnecessary. On the other hand predictable space, including adding parent pointers to cheat, is easy to achieve by counting the total number of nodes or the depth of the tree.

"Constant space tree traversal is impossible..."

Naively I would expect something like left-hand-rule maze traversal to be constant space. The tree may need additional structures to support this sort of travel.

Other thoughts: most state machines are constant space.... there may be something there.

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.

If nodes have pointers to their parent, constant space tree traversal is easy enough.