<p>What are the most common problems that can be solved with both these data structures?</p>

<p>It would be good for me to have also recommendations on books that:</p>

<ul>
<li>Implement the structures</li>
<li>Implement and explain the reasoning of the algorithms that use them</li>
</ul>

There's a course for such things at my university:
CSE 326
. I didn't think the book was too useful, but the projects are fun and teach you a fair bit about implementing some of the simpler structures.
As for examples, one of the most common problems (by number of people using it) that's solved with trees is that of cell phone text entry. You can use trees, not necessarily binary, to represent the space of possible words that can come out of any given list of numbers that a user punches in very quickly.