Suppose I have binary search tree. Each node have two pointers to children and no pointer to the parent.
Is there efficient way to implement iterator without using stack or queue?
By efficient I mean to be able to find next element in O(1) complexity.
Imagine the case of a perfect tree with height h. When the iterator is at the first node (the leftmost leaf), it will need to remember somehow by which internal nodes it arrived at this node, because in one of the next steps it will need to yield the values in those nodes (and their right subtrees). As there are no parent node pointers, this information is not readily available and must be stored somewhere.
No matter how this path is memorised (a list of internal nodes, or a list of directions, like left-left-left-left, possibly stored compactly in bit-representation), the theoretical size of this storage is O(h).
As noted in comments below, storing only directions will require to walk down the path again from the root at each step in the iteration. Alternatively you could memorise the last visited value, and use binary search to find the next node. If all values in the tree are unique, then the memory size of the actual values will have at least the same order of magnitude as a compact path representation (bitwise left-left-left...), so either way (storing the path, or the last visited value) the storage requirements are similar.
Now, as soon as you put some limit on the size of the tree, there is of course no more sense in talking about space (or time) complexity. For instance, if a tree is never going to have a height of more than 64, then the current path can be represented in a 64-bit unsigned integer, with maybe some additional small integer to denote the current size of that path.
As the number of atoms in the observable universe is estimated at 2250, you could work with that as well, and use a 256-bit unsigned integer instead (two longs). Computer memory will never be capable of storing a perfect tree of that height any way.
To summarize: the iterator should have a small size (independent of tree size), and there's also no additional information in the tree nodes. Also, the tree can be unbalanced in any way.
In that case, the answer must be no, from a pigeon-hole principle. The problem is that until you've processed the last node, there's no way to predict how many nodes remain, and how they are related. There's literally an infinite number of options, but the directly available information is finite.
