algorithm - Non-recursive breadth-first traversal without a queue -

in generic tree represented nodes having pointers parent, siblings, , firs/last children, 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 possible iterative (non-recursive) breadth-first (level-order) traversal without using additional helper structures such queue.

so basically: can use single node references backtracking, not hold collections of nodes. whether can done @ theoretical part, more practical issue whether can done efficiently without backtracking on large segments.

yes, can. tradeoff , cost more time.

generally speaking, 1 approach understand 1 can implement traversal without memory in tree. using that, can iterative deepening dfs, discovers new node in same order bfs have discovered them.

this requires book-keeping, , remembering "where came from", , deciding next based on that.

pseudo code 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 , 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   // @ point, know prev child of current   else if (current.next_sibling != null):     prev = current     current = current.next_sibling   // exhausted parent's children   else:     prev = current     current = current.parent     depth = depth - 1 

and then, can have level order traversal with:

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