> I am amazing at whiteboard questions, but that doesn't make me a good engineer. ... A lot of it it is practice 'ooo this looks like a graph problem, let me use a graph', etc.

That actually does make you "a good engineer". The vast majority of developers wouldn't even be able to recognize that much.

Have you worked with any great, experienced engineers who would have had no idea how to traverse a tree?

Yes, and those same great engineers went ahead and figured it out. You see, some are hiring parrots, and others are hiring problem solvers.

I'm all for hiring problem solvers, but how do you differentiate them if you don't ask them to solve problems?

Years of experience is definitely not a guarantee of competence.

Hypothetical interview question: Write a function that finds the distance between two words.

Candidate A: Can recite algos and remembers that Levenshtein distance is the answer.

Candidate B: Has no idea what Levenshtein distance is, writes a brute-force solution with the understanding that it's not an optimal solution. After the interview she spends more time learning what she doesn't know, learns about Levenshtein distance, and sends you an optimal solution via email.

The above is a real-life scenario, so my question to you is - how do you decide who to hire?

This is not a good interview question and neither candidate seems to have answered it well, but I would reject B first because I obviously don't know whether she did any research or whether she just asked Candidate A via StackOverflow