Algorithms for traversing unordered tree
Do you see any way to optimize it further


I don't see why you have (i.e. don't think you should have) while (tmp != NULL) at the top:


On entry you know that this != NULL
You verify that the result won't be NULL before you execute the statement before each continue or break


Removing that would make it slightly faster.



Also I don't understand ...

    if (tmp-&gt;parent-&gt;left == tmp)
    {
      if (tmp-&gt;parent-&gt;right != NULL)
      {
        tmp = tmp-&gt;parent-&gt;right;
        break;
      }
    }


... because if (tmp-&gt;parent-&gt;left == tmp) and (tmp-&gt;parent-&gt;right == NULL) then you do nothing and therefore stay inside while(1) forever. So perhaps either your code is wrong, or one of those if conditions is unecessary.



Apart from the two items above, the existing code looks simple? Multi-threading, using a more-optimizing compiler, or trying to write in assembly are possibilities but not clever. Good optimizations sometimes come from changing the data layout.

For example, one faster algorithm might be to change the way in which the tree is contained in memory: use a custom allocator or similar, to ensure that nodes are physically contained in a contiguous array or vector.

Walking the whole tree would then mean, simply, iterating through the contiguous array: which is pretty quick.

If you do that, it would be easier to change your left, right, and parent pointers to indexes (into the array): because then you wouldn't need to change them if you reallocate (move) the array.

Alternatively keep the nodes in random heap-allocated memory but store the numbers themselves in a contiguous array. Instead of a number member, nodes would have an index member which says which slot in the array contains their number. Making the numbers contiguous (without extraneous tree-node pointers) might be the fastest way to iterate them.