Associating a string with a derived class
Would this solution use memory for every class instance rather than once per class?


Depends on whether your class already contains a vtable pointer or not.

If it does, there will be no additional memory requirements per instance (just another entry in the vtable, which is shared by all instances).

If it doesn't, each class will need an additional vtable pointer (that will be automatically inserted by the compiler to make virtual dispatch work). Also, a vtable will be generated, but those are one per class.

However, since you are already using (and that includes possibly deleting) instances of derived classes via pointer to base class, the base classes destructor (in this case Node::~Node()) should already be marked virtual so the derived classes destructor gets called correctly when deleting the Node*. This means each class should already have a vtable anyways - so no additional per-instance overhead.