3 ms·

Constant space tree traversal is impossible and unnecessary. On the other hand predictable space, including adding parent pointers to cheat, is easy to achieve

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.

somat 1y ago
"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.
- HelloNurse 1y ago
  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).
  - JonChesterfield 1y ago
    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.
    - HelloNurse 1y ago
      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.

somat 1y ago

"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.

HelloNurse 1y ago
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).
- JonChesterfield 1y ago
  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.
  - HelloNurse 1y ago
    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.