There are two fundamental things to teach in an algorithms course:
1) that there are many programs that implement the same algorithm, and many algorithms that implement the same function.
2) that there are a few basic tradeoffs we can make when implementing a function/customising an algorithm: space vs time, read vs write, deterministic vs indeterministic, etc.
I'd guess trees have traditionally been used, because there's a whole zoo of them, which clearly presents (1) and allows (2) to be learned (in "cookbook" style) even if they're never explicitly presented (in "textbook" style).
Suffering is the point. It's like exercises in math or push-ups - if you find a way to do them effortlessly you won't develop the skills you are training for.
