Well, 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

Well, 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.