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.

CodePudding user response：

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)

CodePudding user response：

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.