What is the best object-oriented design approach for a tree with two node types?

Question

I have a tree-like structure as shown in below picture (as one small example). The tree consists of two different node types, that are:

1. Data Nodes: These nodes that are colored in yellow contain about ten attributes. They always appear in the leaves of the tree.
2. Collection Nodes: That are shown in blue. They are sharing Id and Type attributes with the Data Nodes and also keep an ordered list of their children.

This tree is created in one component and sent to another system for manipulation (Saving, showing in GUI, etc.). To design this tree, there are different approaches that I have described below with their advantages and disadvantages. What do you think about them and which one is the most appropriate one in this case?

Approach 1: Have a interface for common functionalities (e.g. getId, getType) and put the specific functionalities (e.g. getChildren) in concrete classes. This way, the other application that needs to manipulate the tree (for saving or showing in GUI), needs lots of down-casing based on the type of the node.

Approach 2: Have one interface for all of the functionalities of both node types. In each concrete class, either implement the method (if applicable) or throw an exception. It is the responsibility of the user to call the right method based on the type of the node.

Approach 3: Do not go for an interface. But just have one class (e.g. TreeNode) with the all data + methods of both node types. It is again the responsibility of the user to call the right method on the right object type.

p.s. The implementation language will be C++11, if it matters.

---

Update 1: More information about this tree and more specific requirements are described below:

1. The tree is created in a source system using a provided API. In this context, the user creates the tree hierarchy and sets the value of each node.
2. The second system that uses this tree, is responsible for saving/loading the tree and also its display in a GUI. These actions usually need walking over ALL nodes of the tree. In addition, this second system can edit the tree elements using the GUI or do a search on the tree for some values.

Answer 1

Another option, besides the three you mention, would be to separate the data to its own class and then have the basic node interface provide both that and children in an optional way.

For the children, this is easy - a node without children simply has zero children.

For the data, you could use std::optional<NodeData&> as the return type, or have two methods (hasNodeData, getNodeData).

This still requires the other code to check for whether there's data there (no way around that, AFAIK), but no other code needs to know about the concrete classes or cast anything.

It's not perfect - you're including NodeData in the top level interface, so if you had a variety of node types that all had different data, this could get unwieldy. But for the case you describe, this would be a fairly clean approach IMO.

.

An approach that could accommodate an arbitrary number of types would be a templated getData method that returned a std::optional for that type of data.

Ex: if(auto fooData = mysteryNode.getData<FooData>()) ...

I think it might be overkill for this situation, but it would be the most general interface.

Answer 2

Approach 1 and 2 are both valid. The key question to chose the most suitable one, is, how uniformly you want to process these objects in the client context (GUI, persistence, ...). The composite design pattern may help you, since it aims to:

Compose objects into tree structures to represent part-whole hierarchies. Composite lets client treat individual objects and compositions of object uniformely.

The main question is whether the uniform handling is desired for a minimal common behavior (approach 1) or if it is expected to be more ambitious (approach 2). GoF mention this issue under two aspects (page 167):

• "Maximizing the component interface": the more common the interface, the more polymorphic will the client code be. However, this risks to conflict with the interface segregation principle if putting udner the same umbrella completely unrelated things.
• "Declaring child management operations" and more precisely at which level:
  • at composite level, it lets you catch issues at compile time, but might imply more risky downcasting. And your client code needs also to cope with the subtle differences of all the concrete classes. This is not in best line with the principle of least knowledge.
  • at component level, it significantly increases uniformity of client code, but if you want to handle different nodes differently in the user interface you'd have to do more checks on the client side to prevent (or handle) exceptions (again an issue with the principle of least knowledge).

So there is no perfect solution: it's a delicate balance to find in view of your intent. Only you can find it.

On thing is for sure: Approach 3 must be avoided. This goes against sound separation of concerns and the open/close principle. This design leads to monolithic code that becomes difficult to maintain over time. Suppose for example, that one day you'd come to the conclusion that you need different type of collections, or different kind of data nodes; it wouldn't be a big issue with approach 1 or 2; but with approach 3 you'd have to review everything !

Answer 3

I see one type of node class only: Node. It has a property ChildNodes which is a list of nodes. This can be empty. Node also has a property Data which may be null. Data is a separate class containing your data properties.

What you call a collection node is a node with children and no data (Data == null). Data nodes have 0 children and a Data object. You can have both (why not?). If you do not like that, throw as soon as a child is added to a data node or data is added to a collection node.