I'm writing only a partial answer, because I currently lack time. That means that I'm not properly sourcing everything, and largely working from my own memory. I don't believe that anything I say below will be wrong, though it is definitely possible that I might be forgetting a few things. In any case, hopefully this will be enough to get you started / ...
Since we're missing a lot of information, this answer will be fairly bare-bones.
There are no "right" or "wrong" answers here. Everything hinges on the goal of the course. And this is as it should be. Usually, you choose the learning goals for the course, and then choose a language that helps you to achieve them.
If the goal is to ...
I think the two situations are entirely different in applications. In the case that the internal nodes are only search keys we find applications in database indices. By associating keys with internal nodes we obtain space efficient dictionary types.
The contrast between the two cases could help learners understand the concepts more easily. By focusing on the ...
I would probably go with expression trees.
2 + ( 6 * x * 3 ) --->
It demystifies something, it's based on pre-existing knowledge, there are umpteen ways to generate practical exercises and it represents an abstract use of the
data type. It's also fun.
In his Algorithms Jeff Erickson discusses and analyses a similar variant, which he calls binary search (a terrible name, if you ask me): For a table of size a power of 2 when searching for key $k$, the idea is to check positions $h(k) \oplus r$, where $\oplus$ is bit-by-bit exclusive or and $r$ is the number of the try. It shares the benefit of quadratic ...