# Trees with duplicate nodes and path cancellations

I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see the whole data structure is as a tree. A picture is worth a thousand words

Each tree node contains an object that I simply represented as an integer. As you can guess, at each layer there are many nodes that are equal. For example, the last layer has 48 leaves; however, there are only two different kind of data in the leaves, namely 11 and 12.

In addition, between each two connected node there may be a bunch of other objects. At each layer, the list are all equal. I've just shown an example using the L_0 array on the two edges of the first layer.

Each layer of the list can be thought as having a label, as shown on the left of the tree. Now, based on some other checks, not relevant for our purposes, some of the paths may be cancelled. The cancellation condition can be thought as

def cancellEdges(node1, node2):
if node1.label == node2.label AND notInPattern(node1.data, node2.data):
deleteEdgesBetweenNodes(node1, node2)


In our example the pattern is shown in the top-right corner. We observe that all the edges between 0 and 8 are useless, which in turn means that the leaves labeled as 8 descendant from 0 should not be reachable. In the same fashion, the edges 1 -> -> 9 and 1->10 are useless. In the picture, this fact is represented by a red background for the nodes whose incoming edge is useless.

At the last layer, the same thing happens. In this case we have also blue nodes, that simply signals that the incoming edge to that node is useless not (only) because of the pattern, but because the parent is red.

In an effort to improve memory occupancy, I simplified the data structure using a linked list, like shown in the image below.

Basically, each element of the L_x lists can be thought of SimpleNode (the array-like objects in the picture); all the nodes belonging to a layer are instead AggregateNode (the elliptic shapes in the picture). The red arrows shows the links between the nodes of the linked list.

class SimpleNode:
data: int
nxt: SimpleNode
prv: SimpleNode

class TreeNode:
data: int
parents: List[TreeNode]
childs: List[TreeNode]

class AggregateNode extends SimpleNode:
tnodes: List[TreeNode]
label: string



Since the edge cancellations may happen only between nodes with the same label, I've decided to use additional pointers to connect the internal tnodes to their parents/childs with the same label. Take care that this parents/childs are not the same ones of the original tree. For example node 9, in the full tree, has 3 parents: 4, 5 and 6; in the linked list it only has 0 as parent.

# Questions

1. How can we keep track of the total number of active paths? It would also be useful to do this incrementally, without having to check the whole tree at the end. In other words, it may be a property of a TreeNode or an AggregateNode or even a global property. In our case, f.e. we should have for the last aggregate node numberOfPaths = 15 or, equivalently, tnode11.numberOfPaths = 10 and tnode12.numberOfpaths=5.

2. How can we expand the whole tree starting from the new linked list? Or also, how can we traverse (depth-first or bread-first, it doesn't really matter) the paths from the list?

3. Is this structure the best we can do? Is there a better data structure that can be used in this case?

• I don't understand what you mean by cancellation or irrelevant properties. – D.W. May 29 '20 at 19:52
• Hi @D.W., I just mean that, basing on some kind of logic properties, one of the path may be deleted. Something like if node1.label == node2.label and isPathDead(node1, node2) then deletePath(node1, node2). – tigerjack89 May 30 '20 at 15:05
• Sorry, the problem statement is not clear to me. Please edit the question; don't just leave information in the comments. Please define all terms and define the task. It's not clear to me what you mean by "keep track of this cancellation". If you want to ask for a data structure, I suggest you define the operations you want it to support, and for each operation, define its semantics (what its inputs are, what its outputs are, and what requirements you want the output to satisfy or what the correct output is). – D.W. May 30 '20 at 20:22
• Hey @D.W. , thanks for the feedback. I tried to modify the question to be a little bit more clear and also show my current (partial) solution. Let me know if it's more clear now. – tigerjack89 Jun 2 '20 at 18:38
• Please distinguish carefully between paths and edges. In some places you use the word "path" but I wonder if you really mean "edge". – D.W. Jun 2 '20 at 23:09