Is it possible to traverse a tree structure (specifically an octree, the 3-D version of a binary tree) by using a fixed sized stack? I do not want to use recursion, since my octree is quite deep.
I am traversing the tree to do a range search problem, to find all the points closest to a queried point. So in my traversal, I do not walk down those subtrees rooted at nodes which my search region does not intersect.
If your octree has parent pointers, I think you can traverse it without a stack at all (see this thread, for example). Without that, you will need a stack that is as deep as the depth of your tree, regardless of how many branches are skipped.
Of course you can traverse a tree without using a deep native call stack, using continuation passing style techniques, or (and this is grossly the same) by making a virtual machine, with its call stack implemented as a heap data, or (yet another point of view) by coding a stack automata with the stack implemented as an explicit heap data structure (e.g. a std::stack).
Think of it otherwise, your C++ naive code could run on a Turing machine, and these beasts don't have any stack.
As Ted Hopp's answer suggests, you might be inspired by Deutsch-Schorr-Waite's Garbage Collection techniques (with a few additional bits per node to temporarily flip the reference direction and remember that) to have a "stack-less" traversal (but you need additional bits in each node). But I believe that having your own stack inside a std::stack or std::vector is probably simpler.
Yes, you can traverse the octree with a fixed-size stack.
The fixed-size just needs to be as big as the longest possible octree depth.
Bear in mind that with an octree, each depth traversal can be recorded with only 3 bits of memory. For each of the three dimensions, you only need to record whether you went in a positive or negative direction.
So even if your octree goes 1000-deep, you can store the recursion with 375 bytes.
