They received a crash course in the power of Haskell ADT and `deriving (Show, Read)`.
Got the job offer too, though I didn’t take it
You were able to demonstrate that you were enthusiastic and knowledge about programming as a whole, which is probably more helpful than what they were originally trying to test for.
No one uses binary trees or some manual form of serialization.
They use "superlib.search(arr)" or (seriliazer.parse(thingy)" and that's about it. No one cares about what it does. They just know it does it faster than something they could write. The only places that care about it are at the utmost peak of scale.
Heck, I run an API that gets tens of millions of reqs a day and I'm an idiot that couldn't computer science their way of of a paper bag.
I feel like people bend themselves out of shape trying to avoid these so-called "complex" or "esoteric" "only theoretical Computer Science" topics. You don't need a general purpose tree or graph manipulation library. Trying to make one ends up creating something far more complex than necessary and all you succeed in doing is making the calling code maybe two lines shorter but also not easily portable between projects, and also at a huge maintenance cost. It would be like trying to make your own, bespoke "Collection handling class" because you think trying to keep track of arrays and lists and dictionaries and sets and queues and stacks is too "complex, esoteric." No, you end up creating something complex and esoteric in the attempt to try to handle the erroneously identified "complexity."
In general, I don't think you can argue definitively on the uselessness of a piece of knowledge from a standpoint of ignorance of that knowledge.
I agree, I think those things are definitely worthwhile learning. But I don't think that it follows we should test for them in interviews.
It sounds like you've done some pretty impressive work around graph algorithms, but if a job doesn't need you to do this, testing for it is a little silly. (If it's a criteria you're explicitly hiring for, I think that's clearly different)
[1] https://aphyr.com/posts/341-hexing-the-technical-interview