Tree data structure where children can only be added based on their type

Question

I have a tree data structure where each node has a name, an id, a type and a number of children. Additionally each node has properties based on its type. Thereby each node with type A should only have children of Type B, C, D... and each node of type C should only have children with type D, E, F, etc.

Therefore I have implemented an abstract class containing all the common fields and subclasses for each type with an additional object for the uncommon properties.
The different types as well as the respective values are stored in an enum.
So I can check if a child can be added to a node using the values of the types defined in the enum.

Do you think it is fine to enforce the structure this way, or is there a better way to accomplsh that?

Answer 1

An abstract class shall not depend on its concrete specialization. This is against the idea of abstraction and totally against the Open/Closed principle.

There are two main approaches for solving your design issue:

• Abstract the rules, for example into an abstract NodeValidator class. In the tree-building process you could then rely on your abstract nodes and the abstract validator. You would inject the validator that is based on the concrete node types in the tree construction.
• Avoid the deep class hierarchy, and opt for an Entity/Component system (a very special case of composition over inheritance). The type verification would the become a component validation. Since ECS allows for runtime composition, you could even imagine to load the component definitions with their properties and the rules from a configuration file, allowing for maximal flexibility.

Answer 2

I have a tree data structure where each node has a name, an id, a type and a number of children. Additionally each node has properties based on its type. Thereby each node with type A should only have children of Type B, C, D... and each node of type C should only have children with type D, E, F, etc.

Implementing this at the data layer is relatively straightforward.

select * 
from permitted_links ; 

+-------------+------------+
| parent_type | child_type | 
+-------------+------------+
| A           | B          |
| A           | C          |
| A           | D          |
| C           | D          |
| C           | E          |
| C           | F          |
+-------------+------------+

select * 
from nodes ; 

+----+--------+------+
| id | name   | type |
+----+--------+------+
|  1 | Node 1 | A    |
|  2 | Node 2 | D    |
+----+--------+------+

select * 
from links ; 

+-----------+-------------+----------+------------+
| parent_id | parent_type | child_id | child_type | 
+-----------+-------------+----------+------------+
|         1 | A           |        2 | D          |
+-----------+-------------+----------+------------+

(OK, I'll admit to a smidgen of denormalisation to get the node Types into the links table but, from the structure as presented, I'm guessing that Types don't change very often, if at all).

The "trick" is that the links table has a foreign key to the permitted_links table, which enforces the parent/child type restriction:

create table links 
( parent_id 
, parent_type 
, child_id 
, child_type 
  foreign key ( parent_type, child_type ) 
  references permitted_types ( parent_type, child_type )
);