It generally also helps performance to store tree-like structures in flat arrays, and transform recursive algorithms into loop-based ones (to help data locality and prevent pushing return addresses at each recursion, respectively); if your application allows such changes of course..

In any case, I hope the changes are not hard to incorporate,
and don't hesitate to post again if BSP issues seem to pop up!