Non-recursive breadth-first traversal without a queue

Question

In a generic tree represented by nodes having pointers to parent, siblings, and firs/last children, as in:

class Tnode {

    def data
    Tnode parent = null
    Tnode first_child = null, last_child = null 
    Tnode prev_sibling = null, next_sibling = null 

    Tnode(data=null) {
        this.data = data
    }
}

Is it possible to do an iterative (non-recursive) breadth-first (level-order) traversal without using any additional helper structures such as a queue.

So basically: we can use single node references for backtracking, but not hold collections of nodes. Whether it can be done at all is the theoretical part, but the more practical issue is whether it can be done efficiently without backtracking on large segments.

For BFS you need a queue anyway. You can invent something yourself, and it will be a queue. — SashaMN, Jan 15 '16 at 22:58
@TimothyShields Why are you so confident? It is very much possible, assuming one has a link to the parent (and he does). — amit, Jan 15 '16 at 23:08
@amit Ok. We can't do BFS without queue in O(|E| + |V|) time. — SashaMN, Jan 15 '16 at 23:14
(1) The question does not ask for O(|E|+|V|) time. (2) `|E|=|V|-1`, since it's a tree, so `O(|E|+|V|) = O(|V|)`. (just mentioning) — amit, Jan 15 '16 at 23:15
It seems to me that implementing tree traversals "iteratively without extra memory" requires normally *more* memory than doing the same "recursively with extra memory" :). If you do it "recursively," you normally just need a stack data structure (no need to use C call stack) of size equal to the depth of the tree, but to do the same "iteratively," you normally need to allocate extra memory for each node of the tree (possibly exponentially more memory, than for recursion). For example, recursive search does not require keeping pointers to parent nodes. — Alexey, Mar 12 '19 at 09:48

score 5 · Answer 1 · edited May 23 '17 at 12:23

Yes, you can. But it will most likely be a tradeoff and cost you more time.

Generally speaking, one approach to do it is to understand one can implement a traversal without extra memory in a tree. Using that, you can do Iterative Deepening DFS, which discovers new node in the same order BFS would have discovered them.

This requires some book-keeping, and remembering "where you just came from", and deciding what to do next based on that.

Pseudo code for your tree:

special_DFS(root, max_depth):
  if (max_depth == 0):
    yield root
    return
  current = root.first_child
  prev = root
  depth = 1
  while (current != null):
    if (depth == max_depth):
      yield current and his siblings
      prev = current
      current = current.paret
      depth = depth - 1
  else if ((prev == current.parent || prev == current.previous_sibling)
           && current.first_child != null):
    prev = current
    current = current.first_child
    depth = depth + 1
  // at this point, we know prev is a child of current
  else if (current.next_sibling != null):
    prev = current
    current = current.next_sibling
  // exhausted the parent's children
  else:
    prev = current
    current = current.parent
    depth = depth - 1

And then, you can have your level order traversal with:

for (int i = 0; i < max_depth; i++):
   spcial_DFS(root, i)

Your explanation on the trade-off is clear - and thanks for taking the time with the code. — Basel Shishani, Jan 15 '16 at 23:31

Non-recursive breadth-first traversal without a queue

1 Answers1

Linked