If a new opendir/readdir option was introduced that allowed returning the same directory entry twice, would that be easier to implement? Then you could go back to the earliest known node you have already passed if the tree gets rebalanced, which at least feels to me like a simpler problem to solve. And for extreme cases like an NFS server restart you could go back to the start of the dir.