There are many problems where the best solution is to adapt either a generic tree you previously created yourself (such as the link to your own code you give as an example) or, I would suggest, the Boost graph library: http://www.boost.org/libs/graph/doc/index.html. However, this isn't one of them.

You mention appending/insertion at the end. This is an example of an invariant that profoundly affects both the data structure and the algorithms that use it. You couldn't just slot in your own algorithms for this data structure using the visitor pattern, for instance, without risking this and other invariants. Take the search routines. They rely on the properties of the data structure. You might want to modify their behaviour through the templates provided, but the algorithm itself is tied intimately to the data structure.

What I think is more interesting is the 'skin' that you put on top of your creation, manipulation and search routines: what they are called and how you use them. This is where there is some separation between layers. It leads to the structural conformance issues that I discuss in the text.

Other issues:
Could you use polymorphism instead of templates?
Yes, but why would you want to?

Are method defns inlined if inside class defn?
Not necessarily. If you feel strongly about this, you can generally prevent your compiler from doing it.

Is this usually not a good idea?
No, it usually is a good idea. But you should test whether it helps or not on a case-by-case basis.

> I believe that in the first example in the article (the
> crossword clue-solving algorithm), the second for loop
> should read:
> j < csyns->size();
> instead of
> j < csyns.size();

Thanks for pointing this out. I will arrange for it to be changed.