3 ms·
I think the intention is that you keep a record of what x is in the current node, and at every node above the current node. In the recursive implementation whic
by dmurray 1y ago
I think the intention is that you keep a record of what x is in the current node, and at every node above the current node. In the recursive implementation which the author describes as equivalent, these values are kept in the stack.
- bee_rider 1y agoSeems a bit inefficient… I guess we can delete the a node’s copy of x after all of a node’s child nodes are visited, at least.
- dmurray 1y agoWell, it doesn't need to be any worse than the stack-based implementation of a recursive tree traversal, and it can't be significantly better. You have to store that state somewhere. Perhaps it can be optimized to be a little better than the recursive version, depending on how much overhead your language uses for a stack frame that it won't need for this special case.