Iterative octree traversal

Question

I am not able to figure out the procedure for iterative octree traversal though I have tried approaching it in the way of binary tree traversal. For my problem, I have octree nodes having child and parent pointers and I would like to iterate and only store the leaf nodes in the stack. Also, is going for iterative traversal faster than recursive traversal?

Answer 1

It is indeed like binary tree traversal, but you need to store a bit of intermediate information. A recursive algorithm will not be slower per se, but use a bit more stack space for O(log8) recursive calls (about 10 levels for 1 billion elements in the octree). Iterative algorithms will also need the same amount of space to be efficient, but you can place it into the heap it you are afraid that your stack might overflow.

Recursively you would do (pseudocode):

function traverse_rec (octree):
    collect value  // if there are values in your intermediate nodes
    for child in children:
         traverse_rec (child)

The easiest way to arrive at an iterative algorithm is to use a stack or queue for depth first or breath first traversal:

 function traverse_iter_dfs(octree):
     stack = empty
     push_stack(root_node)
     while not empty (stack):
         node = pop(stack)
         collect value(node)
         for child in children(node):
             push_stack(child)

Replace the stack with a queue and you got breath first search. However, we are storing something in the region of O(7*(log8 N)) nodes which we are yet to traverse. If you think about it, that's the lesser evil though, unless you need to traverse really big trees. The only other way is to use the parent pointers, when you are done in a child, and then you need to select the next sibling, somehow.

If you don't store in advance the index of the current node (in respect to it's siblings) though, you can only search all the nodes of the parent in order to find the next sibling, which essentially doubles the amount of work to be done (for each node you don't just loop through the children but also through the siblings). Also, it looks like you at least need to remember which nodes you visited already, for it is in general undecidable whether to descend farther down or return back up the tree otherwise (prove me wrong somebody).

All in all I would recommend against searching for such a solution.