At the risk of focusing on your specific example, rather than your larger point which is a good one: If you're talking about balanced trees, I sort of agree wi

At the risk of focusing on your specific example, rather than your larger point which is a good one: If you're talking about balanced trees, I sort of agree with you. That's the kind of algorithm where it makes sense to write it once, test it thoroughly, stick it in a library and never worry about it again. But there are plenty of other uses for tree-like things. Think filesystems, or the HTML DOM, or JSON documents, or (generalizing a bit) dependency graphs, and so on... I actually like tree problems. You can take something with practical significance (laying out a web page, or syncing two directories, or simplifying a boolean expression) and strip away the details of the situation to get to a core algorithm that depends only on the tree's structure. In my experience, the biggest factor in how well interviewees cope with kind of question is their ability to reason clearly about what their code is doing, instead of just pattern-matching from their previous experience.