> In my experience, people start complaining that an interview is "theory-heavy" at about the point that you expect them to know when and how to use a binary tree. Binary trees are not hard-core CS theory, they are freshman Intro to Data Structures.

The other part about binary trees is by their very nature they involve pointers and recursion. Understanding pointers and recursion is the difference between being able to write code and being a programmer. The former is a fundamental skill any knowledge worker should have (scientists and financiers using Matlab or Python, statisticians using R); the latter takes passion, effort and talent.

The other extreme I've seen is asking questions from computational geometry, combinatorics and complexity theory (for generalist software engineering positions). These are all relevant skills and for the former two a good cursory knowledge is important for a generalist: however, unlike pointers or recursion they're not as fundamental to programming.