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

Here's a sketch of the algorithm. Very inefficient, but satisfies your requirement of only using O(1) additional space.

1. Node* GoRight(Node* c)
   If c is root (there's no parent), return NULL
   Let p be the parent of c. Find its child r immediately to the right of c (may need to do a linear search of p's child links). If found, return r
   If not found (c is the right-most child), set c=p, repeat from the start.

The node thus found may be at a higher level than the node we started with.

2. Node* GoDownToLevel(Node* p, int k)
   If p is NULL, return NULL
   If p is at level k, return p.
   Starting from p, follow the left-most child links down until level k is reached or there are no links to follow. Let c be the node thus found. If c is at level k, return c.
   Otherwise, c is a leaf node at a level above k. Set p = GoRight(c), repeat from the start.

3. Node* NextAtLevel(Node* c, int k)
   Return GoDownToLevel(GoRight(c), k)

4. Node* NextInBFSOrder(Node* c)
   Let k be the level of c. Let r = NextAtLevel(c, k). If r is not NULL, return r.
   Otherwise, traverse the parent chain all the way to the root, return GoDownToLevel(root, k+1). Alternatively, root could be stored in the iterator. Alternatively, the iterator could keep track of the leftmost child of the first non-leaf node it encountered while traversing level k, and jump to that child once NextAtLevel fails; this child starts the iteration at level k+1.

---

Reverse BFS would work similarly. The hard part is finding the node to start the traversal from. Basically, perform GoDownToLevel(root, infinity) while keeping track of the deepest level encountered and the first node encountered at that level. And of course, do GoDownToLevel(root, k-1) instead of GoDownToLevel(root, k+1) when NextAtLevel fails.

If you keep track of the height h of the tree while its being built, then you can start the traversal with GoDownToLevel(root, h)