Iterating over binary tree w/o control of stack or dynamic allocation

Question

Is there an efficient, practical way to iterate over a binary tree given the following constraints:

1. You do not have control of the call stack, and thus may not use recursion. All state must live inside the iterator/range object, not on the stack.
2. No heap allocations may be used anywhere in the algorithm.
3. The tree may be immutable, and thus you cannot store iteration state inside it.
4. You don't have parent pointers.
5. The iterator/range struct must not be so large that it's completely unreasonable to pass to functions.

Edit:

1. This is not homework. I actually am trying to design a library that builds binary trees on a second stack and makes lots of guarantees about heap allocations (or lack thereof).
2. The trees are balanced. (They are AVL trees.)

Answer 1

It can be done only for trees up to a certain limit in depth (and therefore in number of elements) because it requires auxiliary memory proportional to the tree depth; at the time you're iterating on an item, you need to keep track of what item to proceed to next, and if you're at one of the deepest leaves then the number of "keeping-track pointers" that are required will be just 1 less than the depth of the tree. For example, if you can accept being limited to a depth of 32 (and therefore no more than 4,294,967,295 nodes), an auxiliary fixed-size array of 32 pointers (plus an index on it) will be needed.

For binary trees that aren't totally degenerate (and thus have a number of nodes roughly proportional to 2**depth, not just to depth;-), this fixed amount of auxiliary memory should be acceptable -- i.e., just fixed auxiliary memory on the order of log(N) pointers to iterate on any tree with up to N nodes. If this is not acceptable, then the answer to your question "is there...?" is no;-).

Answer 2

If your tree is guaranteed to be sorted on its values and those values are strictly ascending (all B > A, not just B >= A), then you can traverse trees of unlimited size using no dynamic memory. You do take a performance hit, though.

To find the next value after value A, just descend into the tree again, doing a binary (of course) search for a value just larger than A.

I just thought this up. If someone can prove my thinking wrong, go ahead!