story
I think what I see as the real concern is a case of "not knowing what you don't know." If you aren't exposed to at least the fundamentals of this broad base of CS knowledge you aren't going to know that they are available to you when you need them. Learning about a tree when you first read about it is great. But that person will still have huge gaps in their CS knowledge compared to someone who systematically studied it.
I also don't think this is so much about having a CS degree, as it is simply having studied CS in some fashion. I've worked with plenty of talented self-taught developers who took the time to learn these things on their own.