Limited space iterators

Question

I've implemented a tree (not a binary tree, every node can have several child nodes). For every node, we can access its level in the tree, its children and its parent node.

The next phase is to implement 2 iterators for this tree but the catch is I can not save more than a constant amount of information to help complete these iterators (i.e constant space complexity).

My questions are, given a node n that I'm currently at:

1. What would be the algorithm to find the next node to traverse in a BFS order?
2. What would be the algorithm to find the next node to traverse in a *Reverse BFS order?

*Note:

Reverse BFS is traversing the levels in reverse order e.g Reverse BFS of the following tree

      1 
    / | \
   2  3  4
  /  / \  \
 5  6   7  8

would be 5 6 7 8 then 2 3 4 and then 1.

Answer 1

I assume you can figure out how to do an pre-order traversal of the tree: Take the root first, then go to the first child till you hit a node with no children. Then go to the parent and find the next child after the one you came from. If it was the last child repeat with the new parent.

Do this once to find out the deepest node of the tree, or have the tree store its max depth. Then do it again stopping at the first child with that depth. Your iterator is that depth and the address of the child.

To increment the iterator keep doing pre-order traversal on the child and skip all the nodes where node->depth != depth. Each time the traversal finishes decrement depth. When depth becomes negative return end().

Note: in the pre-order traversal you can skip going down to children when node->depth == depth, go straight back to parent.