When was the last time we needed to know the optimal solution for traversing a binary tree in my day-to-day coding tasks? Unless we are building the next Google Search Algorithm, I highly doubt it's relevant

Those are interviews that just find questions online... Give relevant exercises that matter for the company.

Also I understand they want to check some kind of intelligence, but be honest, how many do stuff like that based on the pythagorean theorem we learned in school ? Pretty sure we all just google the solutions we need.

As it's a solved problem you never need to know it. Just use one of the algorithms that suit your particular use case best. Most likely there is already a highly optimized/debugged implementation too.

So even in the rare case you need something like that you don't have any advantage memorising that shit.

I do not know. I just know that if I give them the answer to those questions the number they give me goes up by a lot.