I always stipulate that they can use whatever brute force approach they want, and that i'm not judging on the algorithm. (Though we'll then discuss the big O complexity of what they've done and i'll ask them to brainstorm some avenues for optimization).
The main drawback of this particular problem is that it's biased toward people with more formal CS experience who have probably seen more tree and graph stuff, when i'm not really trying to measure for that experience directly.
I'd be interested in a problem that doesn't have that aspect but still takes up a fair bit of brain space when thinking through. What I mean by that is that when you're trying to build and debug something recursive, you have to hold in your mind some representation of what the stack will be at various points, and not everyone has a great aptitude for that.
It seems to me to still be very poorly understood in general that the purpose of a question in an interview is not to see if the candidate gets the right answer, but to see how they function. (In those interested enough to read the discussion this deeply it's probably somewhat better understood.)