They're both occasionally the best tool for the job, but I think they're hugely overrepresented in that type of interview. I haven't found that they come up very often in most web development, as an example, but they definitely come up in interviews for web developers.

Since all programming jobs deal with trees and recursion, and if you are already at Google working on another team, wouldn't it mean you already know about those (since our assumption being all jobs deal with those)? Why not just check directly if you were actually useful instead?

It's 100% not true that all programming jobs deal with trees. I worked for years on a major audio/video/screensharing communications SaaS product and never once needed to write recursive code or use a tree structure. Not all code is for processing data. There was tons of code that had very little to do with data structures or algorithms, and much more to do with implementing network protocols, business logic, managing state, abstracting the differences between the various operating systems we had to support, etc...

I was just taking GP's statement and shows that it is not consistent with the rest of his argument.

I don't agree that all jobs have to deal with trees either.

I don't think people understand that when you work at scale, efficient data structures and algorithms actually matter. I doubt there are many positions in Google that don't fundamentally require the ability to understand both.

Trees as data structures are inevitable. Did you have to balance them or perform other nontrivial graph theoretic transformations though?