I've just had a quick glance at the question. You could use a variation of the pre-order traveral with a counter (passed as a reference parameter) to each recursive call.
I'll have to give it a bit more thought to get the particulars sorted - but something along this line should work.