It depends on which part of an interview you are talking about. Big O notation has never been talked about in my daily work, but you absolutely need to make your code perform well when you write it. I've never had to specifically traverse a binary tree, but I absolutely need to be able to process data in a single pass, and I constantly am iterating through something or another.

So if you think you are being tested on being able to recite CS algorithms, the answer is "almost never". But if you think you are being tested on, "Can you solve a problem with code, and make it perform well?", the answer is "Every day."