[c++] non-recursive way to iterate tree

This is simply a breadth-first search. It may be breadth-first for multiple reasons.

1. It avoids recursion that leads to stack overflow.

2. It finds the closest node to the root matching the supplied name, which seems to be what would be most useful.

That method is functionally identical to recursion, the only difference being that you have to manually manage your own stack, rather than using the machine stack.

At best, any speedup will be minimal - the time complexity is still linear in relation to the number of nodes in the tree.

What makes you think that recursion is too slow?

I have always listen that recursion is slow because of the cache miss.

For a QuickSort algorithm the solution is to have a MaxLevel variables en switch to InsertionSort if MaxLevel is reached.

For a a scene tree the best solution is to use recursion ?

I have always listen that recursion is slow because of the cache miss.

No, "recursion is slow" is a false statement. There are situations where recursion might be slow, and then it has nothing to do with cache misses.

For a QuickSort algorithm the solution is to have a MaxLevel variables en switch to InsertionSort if MaxLevel is reached.

That's a solution to a specific problem of QuickSort, and not to a general problem with recursion.

For a a scene tree the best solution is to use recursion ?

Best solution to what?

Best solution to what?

To traverse the tree for saving the scene, find an object by name or pointer, update each object and render the scene.

Write your code to be clear. If performance is a problem, use a profiler to see where the time is going. After that, if you find that traversing the tree is actually a performance bottleneck, then you can worry about this.

That method is functionally identical to recursion, the only difference being that you have to manually manage your own stack, rather than using the machine stack.

At best, any speedup will be minimal - the time complexity is still linear in relation to the number of nodes in the tree.

What makes you think that recursion is too slow?

It might be worthwhile to mention that the heap usually is a lot bigger than the stack which alows for deeper traversal so both solutions are not exactly identical.

It is very likely that this won't be a limiting factor though.

About performance:

Always profile and benchmark.

If it's not too slow you don't have to care.

Otherwise it might be possible that std::stack is implemented as some kind of list with nodes allocated one by one which might lead to more cache misses than a contiguous block of stack memory which the recursive version would use.

To traverse the tree for saving the scene, find an object by name or pointer, update each object and render the scene.

If you want to avoid cache misses when traversing a tree, then make sure that the tree's elements are stored contiguously in memory, in the order that they will be traversed. That way, it's the same as iterating through a linear array.

If the operation that you need to perform is "for each object", then you shouldn't even be using a tree in the first place, you should just have an array.

If the operation is "find object by name", then you want a hash map from names to object-pointers.

Otherwise it might be possible that std::stack is implemented as some kind of list with nodes allocated one by one which might lead to more cache misses than a contiguous block of stack memory which the recursive version would use.

I don't think that can happen: By default std::stack uses std::deque as its underlying container (std::stack is not a container, but a container adaptor). There are multiple possible implementations of std::deque, but they won't be one-node-per-item implementations because of the performance guarantees (O(1) random access iterators).

It's possible to get a one node per item deque implementation with a dynamic array containing pointers to the individual nodes, which gives you the constant time random access. Some standard library implementations have an N item per node implementation where N shrinks as sizeof(T) increases, which degenerates to N equals one after a point. IIRC, at least some versions of MSVC's standard library implementation work this way.

Oh sorry, it would be a breadth-first search, if the items were going in one end of the data structure and out the other end.

On second examination, this does not appear to be the case.

For a a scene tree the best solution is to use recursion ?

Usually a world has multiple data structures involved.

A scene or level or world is usually going to be used for many frequent searches and lookups. Queries are both for existence and also for position. There will be frequent changes to objects in the world.

Generally there is a hash table containing all the objects. The hash should be a guid assigned to each object. This is generally the master list.

There is also generally a spatial tree, such as a loose quadtree, that indicates where the guid lives in the world. When an object's position is updated this spatial tree needs to also get updated.

There may be yet another graph, called the scene graph, used for display. Quite likely this graph is not part of the game world since it is part of the renderer's responsibility, not world management's responsibility.

Do you mean to have a root node and have children in it and have with that an array of SceneObject who is just all objects ?

Use the recursion to save/load and the array for other operations ?

Do you mean to have a root node and have children in it and have with that an array of SceneObject who is just all objects ?

The idea is that you don't use a single data structure for everything. Many old engines tried to put absolutely everything into a "scene graph" (one graph to rule them all), which was a massive tree with a root node like you're describing, but that's a really bad idea. Data that's used for different purposes should be stored in different ways.

struct TransformNode
{
	Mat44 local;
	Mat44 global;
	vector<TransformNode*> children;
};

struct BoundingSphere
{
	Vec3 position;
	float radius;
};

struct Actor
{
	TransformNode* transform;
	BoundingSphere* sphere;
	Mesh* mesh;
	Material* material;
};

struct Scene
{
	TransformNode* rootTransform;//tree of data
	vector<BoundingSphere> spheres;//array of data
	list<Actor> actors;//linked list of data, pointers into the above array and tree
};