When to Use Template VS Inheritance

When should I use templates instead of inheritance, and vice versa?

If you know during compile-time what objects you're going to manipulate, then static polymorphism with templates is often the fastest way to go, and it produces code that's a little bit more concise (no need for explicit inheritance). It can also be more generic as you're not restricted to a strong class hierarchy.

If you want run-time polymorphism, then you have no choice but to use pointers, inheritance and the slight overhead of virtual functions.

My own opinion:

Use templates when possible, it's comfortable
Use inheritance to factorise code (but not to have heterogenous collections), but be careful with slicing.
Don't worry about the performance issues of virtual calls
Sometimes you have no choice and you want hetergenous collections dragging around the pain of using pointers

C++ metaprogramming vs inheritance

Like many questions of this kind, the "crucial factor" depends on the application of the code.

What's more important, compilation times, code complexity, or speed of execution?

If you intention is to make the compile-times faster (due to project size, or older-build servers), you want to avoid templates, every code-change to a template will rebuild all source-files the template-headers are included in.
If your concerned about execution times, templates often allow for you to produce code that the compiler can optimise specifically for the types in question, however inheritance allows you to optimise the code specifically for each type (with the added vtable-lookup times). Thus you'd need to benchmark trail code for both.
If your concerned with code-complexity (and that for most modern applications is the biggest priority) It depends on both the skill of other developers on the project, as well as the number of template specialisations you'll need.

In regard to the last point, gauging that requires a complex understanding of the task beyond the scope of this question, however my advice is simple; if you would require anywhere near as many specialisations as you have types - use inheritance instead. For something like your example node-tree, inherited types will provide a much better solution for the average developer to work with, if however you needed a "works for everything" method or function (such as a stream << operator) using a template would be a better recourse.

tl;dr

Unless you have a specific processing/memory overhead to worry about, use the one that creates the smallest-amount of code. Aim for clean, clear and easy to read.

C++ concept check vs inheritance

I think of concepts as a kind of meta-interface. They categorize types after their abilities. The next C++ version supplies native concepts. I hadn't understood it until i came across C++1x's concepts and how they allow putting different yet unrelated types together. Imagine you have a Range interface. You can model that with two ways. One is a subtype relationship:

class Range {
    virtual Iterator * begin() = 0;
    virtual Iterator * end() = 0;

    virtual size_t size() = 0;
};

Of course, every class that derives from that implements the Range interface and can be used with your functions. But now you see it is limited. What about an array? It's a range too!

T t[N];

begin() => t
end() => t + size()
size() => N

Sadly, you cannot derive an array from that Range class implementing that interface. You need an extra method (overloading). And what about third party containers? A user of your library might want to use their containers together with your functions. But he can't change the definition of their containers. Here, concepts come into game:

auto concept Range<typename T> {
    typename iterator;
    iterator T::begin();
    iterator T::end();
    size_t T::size();
}

Now, you say something about the supported operations of some type which can be fulfilled if T has the appropriate member functions. In your library, you would write the function generic. This allows you accept any type so long as it supports the required operations:

template<Range R>
void assign(R const& r) {
    ... iterate from r.begin() to r.end(). 
}

It's a great kind of substitutability. Any type will fit the bill that adheres to the concept, and not only those types that actively implement some interface. The next C++ Standard goes further: It defines a Container concept that will be fit by plain arrays (by something caled concept map that defines how some type fits some concept) and other, existing standard containers.

The reason why I bring this up is because I have a templated container, where the containers themselves have a hierarchical relationship. I would like to write algorithms that use these containers without caring about which specific container it is. Also, some algorithms would benefit from knowing that the template type satisfied certain concepts (Comparable, for example).

You can actually do both with templates. You can keep having your hierarchical relationship to share code, and then write the algorithms in a generic fashion. For example, to communicate that your container is comparable. That's like standard random-access/forward/output/input iterator categories are implemented:

// tag types for the comparator cagetory
struct not_comparable { };
struct basic_comparable : not_comparable { };

template<typename T>
class MyVector : public BasicContainer<T> {
    typedef basic_comparable comparator_kind;
};

/* Container concept */
T::comparator_kind: comparator category

It's a reasonable simple way to do it, actually. Now you can call a function and it will forward to the correct implementation.

template<typename Container>
void takesAdvantage(Container const& c) {
    takesAdvantageOfCompare(c, typename Container::comparator_kind());
}

// implementation for basic_comparable containers
template<typename Container>
void takesAdvantage(Container const& c, basic_comparable) {
    ...
}

// implementation for not_comparable containers
template<typename Container>
void takesAdvantage(Container const& c, not_comparable) {
    ...
}

There are actually different techniques that can be used to implement that. Another way is to use boost::enable_if to enable or disable different implementations each time.

c++ templates and inheritance, can templates be more selective

If you want to only allow only Ts that derive from a certain interface you can use SFINAE (substitution failure is not an error). Here is an example:

#include <type_traits>

struct Base {
    virtual ~Base() = default;
};

struct Derived : Base {};

struct NotDerived {};

template <class T, class = std::enable_if_t<std::is_base_of_v<Base,T>>>
struct TClass {};

int main ()
{
    TClass<Derived> tc1;
    // TClass<NotDerived> tc2; // compiler error
}

If you have c++20 concepts then you can do the following:

template<typename T>
concept DerivedFromBase = std::is_base_of_v<Base,T>;

template <DerivedFromBase T>
struct TClass {};

If you use a type which does not inherit from Base you'll get a compiler error.

C++ policy based design: Inheritance vs composition

One possible reason: when you inherit from CheckingPolicy, you can benefit from empty base class optimization.

If CheckingPolicy is empty (i.e. it has no non-static data members other than bit-fields of size 0, no virtual functions, no virtual base classes, and no non-empty base classes), it will not contribute to the size of MyContainer.

In contrast, when it is a data member of MyContainer, even if CheckingPolicy is empty, size of MyContainer will be increased by at least one byte. At least, because due to alignment requirements you could have additional padding bytes.

This is the reason why, e.g., in the implementation of std::vector you can find ihnehritance from an allocator. For example, libstdc++'s implementation:

template<typename _Tp, typename _Alloc>
struct _Vector_base {
    typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
        rebind<_Tp>::other _Tp_alloc_type;

    struct _Vector_impl : public _Tp_alloc_type, public _Vector_impl_data { 
        // ...
    };

    // ...
};

Stateless allocators (like CheckingPolicy with no non-static data members) will not contribute into std::vector's size.

In C++20 we'll have [[no_unique_address]] to potentially address this issue: whereas empty base optimization is required for standard layout types, [[no_unique_address]] is just a permission, not a requirement. (Thanks Nicol Bolas for pointing that out.)

When to use templates rather than derived classes

templates vs class hierarchy

The main thing is the cost of the virtual function calls. If the computational cost of the actual wok of the function is small then the cost of virtual dispatch can be significant. This is especially the case compared to an inlined function and if used inside tight loops.
Using runtime polymorphism rules out the possibility of functions being inlined.

C++ templates are a very powerful tool to have...

Along with the well known generic containers and algorithms like you find in the C++ standard library, C++ templates support a range of advanced techniques such as:

Policy based design
Template meta-programming

Essentially you are programming the compiler to build the classes you wanted. Used well this can give highly reusable optimal code. If misused it can give much more bloated object code than a more appropriate approach.

c++ standard practice: virtual interface classes vs. templates

You're basically right, dynamic polymorphism (inheritance, virtuals) is generally the right choice when the type should be allowed to change at runtime (for example in plugin architectures). Static polymorphism (templates) is a better choice if the type should only change at compile-time.

The only potential downsides to templates are that 1) they generally have to be defined in the headers (which means more code gets #included), and this often leads to slower compile-times.

But design-wise, I can't see any problems in using templates when possible.

Which complies more with standard c++
style?

Depends on what "standard C++ style" is. The C++ standard library uses a bit of everything. The STL uses templates for everything, the slightly older IOStreams library uses inheritance and virtual functions, and the library functions inherited from C uses neither, of course.

These days, templates are by far the most popular choice though, and I'd have to say that is the most "standard" approach.