Ah! THERE it is! I remembered that I had an article out there somewhere where I had documented that the example code actually ran twice as slow in the presence of what seemed like the right index to use and I found it. It's in the article at the following link. You can certainly setup the test data from the article and give it a try yourself with the understanding that index requirements can and do vary from machine to machine if you consider available memory, number of processors, MAXDOP settings, etc.
http://www.sqlservercentral.com/articles/T-SQL/94570/
The quote from the article is...
Also notice that we didn’t add any indexes. It turns out that adding an index to the EmployeeID column would actually make the upcoming code run about twice as slow even though we’d get a MERGE JOIN out of it. Do NOT add an index to this interim table! If you intend to keep this table with the Nested Sets calculations (the Left and Right Bowers, etc) in it, add the indexes you'll need AFTER we get done with the rest of the steps below.
Like I said, "It Depends" and no one should ever take on the attitude that "INdexes is definitely a MUST thing here or everywhere." Adding indexes without analysis and testing can be the worst thing to do.
--Jeff Moden
Change is inevitable... Change for the better is not.