A tree? Maybe not...

So, how about that tree? It's tempting to do something like van Laarhoven describes, though I'd be tempted to put maxima on the left links, minima on the right links, to assist with the range check. But wait a minute. Now that we have added the purely combinatorial part, we never actually generate and selectively count more than one power of ten's worth of palindromes at a time, and at least some of those are of the trailing edge of an interval that covers a power of ten. Since the first d-digit Y is 1, for d == 1, or 10^(d-1) + 1, for d > 1, for them it's not like we have to skip a lot of Ys to find those of interest. That leaves the leading part, either [m..n] or [m..tenToThe mdigits - 1]. Just how many Ys are there for a given number of digits, anyway?

*Main> map numNDigitYs [1..50] [3,2,5,3,8,5,13,9,22,16,37,27,60,43,93,65,138,94,197,131,272,177,365,233,478,300,613,379,772,471,957,577,1170,698,1413,835,1688,989,1997,1161,2342,1352,2725,1563,3148,1795,3613,2049,4122,2326] 
*Main>

OK, up to 4122 is a bit long to grind through.

We can do some things:  for small d, might as well just scan as we are now. For bigger d, though, we have the one or two two-2 palindromes at the high end, and at the low end, 10.....01, optionally 10..020..01, and then no-2s and optional one-2s interleaved up to 11110...01111 (d even) or 11110..010...01111 (d odd) for d > 9. If d is 3 or 5, then the largest non-two-2 Y is 121 or 11211, else for d <=9 it's 111...111.

So, for sufficiently large d, if the first two digits of m are > 11, then there are at most two (the two-2 flavor) Ys in [m..n], depending on the parity of d (whether it's odd or even) and the value of n.

This will help when it lets us rule out no-2 and one-2 Ys, but when we have to dig into those, which account for the vast majority of the Ys with a given number of digits, we're back to scanning that list. Doing it right means coming up with a better data structure, one that lets us quickly determine how many values are in a given range.

Hmmm... come to think of it, can we get away with just generating the digits that suffice to determine each Y? Maybe those are easier to work with--it would certainly let us dump all the calls to backwards, which still takes a fair amount of time. The only issue will be the range checking--which we'd have to recast in terms of the half-palindromes. (UPDATE: Sigh, I guess not. You'd be doing it repeatedly rather than just once.)