# how to iterative tree traversal

This topic is 3872 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a tree data structure that I use for my scene graph that I traverse each frame to update 20.000 nodes, I am currently doing the typical recursive traversal but probably it would be quicker if I converted the recursive traversal in an iterative one, does anyone have any hint on how to do that? Here is how my data structure looks like:
class Node
{
public:

... some data ...

std::vector<Node*> Children;
};

void do_something_before(Node*)
{
...
}

void do_something_after(Node*)
{
...
}

// function to translate into an iterative one

void traverse(Node* node)
{
do_something_before(node);

for(int i=0; i<node->Children.size(); ++i )
traverse(node->Children);

do_something_after(node);
}

Thanks

##### Share on other sites
No, it wouldn't be quicker. The traversal is insignificant compared to the work done on individual nodes anyway. If you really wanted, you could turn it into an O(1) algorithm in terms of memory usage by using parent pointers, instead of a stack, but this wouldn't speed up things one bit.

##### Share on other sites
Quote:
 Original post by Michele Bosiprobably it would be quicker if I converted the recursive traversal in an iterative one

Unlikely. Anyways, if you want to do depth-first graph traversal, you need to use a stack. In the case of recursion, this is implicit; the stack used is the call stack. For iteration, you'll need to keep an actual stack around. The algorithm is as follows.

push the root node onto the stackWhile the stack is not empty:  pop a node off the top of the stack  push the children onto the stack  do any node drawing stuff you like

The do_something_before() is trivial to add to this. The do_something_after(), not so much. Probably the easiest way to implement it is to allow a Node to detect when it is the last child of its parent; it can then handle that stuff. The alternative is to have a second stack of indices into the first stack, so you can tell when a particular subtree is completed.

##### Share on other sites
Thank you guys, it seems that the solution is quite complex and probably now worth the time spent on it :(

##### Share on other sites
You might find that the best gain you can easily get out of such an algorithm is to allocate your Node objects from a pool or a pre-allocated array, thus making more effective use of the memory cache when traversing the tree. Obviously it also helps if you can keep the Nodes as small as possible.

##### Share on other sites
Thanks Kylotan, also from other tests I did it turned out that at the level of performances the code is the cache friendliness of the data structures becomes quite important, its easy to see also if one adds some dummy data to the node and does some timings. This is surely the direction I will go and forget about iterative node traversal (for now).

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634087
• Total Posts
3015444
×