Count number of nodes in a binary tree the OO way
I agree with the other posters that a visitor pattern would be a viable solution. One important reason being, that a node usually holds some payload, not just other nodes, and you want to have a mechanism that allows you to be very versatile on what you want to do with the data in the tree.

You may want to count the number of nodes, you might also want to count the number of nodes, where the payload matches some criteria, or you want to count the number of nodes that do not have a left and a right sub node or whatnot. You don't want your node to contain a method for every possible question you want to ask your tree.

You might want to read my blog post on the LOD and structure agnostic access for a rather freaked out, but general solution. But be warned it's possibly not the kind of code you might be used to and you might not find it particularly "pretty", as it trades type safety for "simplicity".

But a visitor is not the only good solution out there. You may prefer to implement a method that returns an iterator, or even a Stream of nodes. This way you could use the Java stream API and be very versatile.

As for the interview: I often feel that programming tasks in interviews are misplaced. The résumé should give you enough of an idea if you've got an experienced programmer or not. Once the person is hired, code conventions, code reviews and tests should shape the quality and style of the person's code to your needs anyway - and there's a probation period to see if the person is not up to your standards or toxic. The only thing that a little piece of code is good for, in my opinion, is to sort out freshmen and students who don't know how to code, but claim to do so. In job interviews I might like to talk about a piece of code and discuss its style, not for the sake of labeling the answers "right" or "wrong", but to see how they think about code: Are they the pragmatic kind of programmer, are they code-poets with a love of style and readability, will you have to brake their tendency for over-engineering or will you have to nurse them a bit more? Do they make good points, are they the timid or the outspoken kind of person? You might feel you lack the one or the other kind in your team and that might make a difference in the end. But I feel that, if I look at a résumé with plenty of projects on it, that I should be able to assume they know how to code and I don't want to insult them with giving them programming tasks that are not related to their daily work at this company, but rather to their first year in algorithms and data structures class.

Discussing your piece of code above, I would, for example find it perfectly reasonable, if the candidate said: "This is a pragmatic solution for counting nodes and maybe something similar, so if that's all there is to it, I'd be fine with it. Still, if it is foreseeable that we need more than just two or three queries, we should have another object do the query." That'd be bang on.