I have a tree structure in my program. I need to find special combinations of vertices that will be added to two lists.
Those lists just need to store labels of those vertices.
Rules for List L1:
1. If a vertex has two children and one of those children has only one child, add it.
2. If a vertex has a child that that have two children, combine them until you meet a vertex with a child with zero or one children, then add the combined labels.
Rules for List L2:
1. If a vertex has one or zero children, add it.
2. If a parent of the vertex also had one child, combine the labels and add them. This should add all parents that have one child until you meet a parent that has two children. We add this combined labels to the list
I know that I propably described it poorly but maybe the example will be more understandable.
Example:
Tree image
List L1 has:
A - Has two children with a child with one child, and only a root parent, we add it.
AA - has a parent (A) with two children, so we combine them. Has a child with zero or one children so we add it.
B - has two children with a child with one or zero children so we add it
BAB - The first be has a child with two children so we add them (we get BA), but because BA has children with two children we can't add it. We need to combine BA and B, because it ha two children, now we can add it to the list
BAC - same as BAB but we check the other branch.
List L2 has:
AC - because it has zero children
C - because it has only one child
CB - B has a parent C with one child so we combine them, parent of C (vertex A) has two children so we can't combine them. Because we got all possible combinations we add it to a list.
Those are unique values, there would be repeats but I just need unique ones.
What I have tried:
Using Depth First Search but I have no idea how to combine vertices in the way that I need to. I can do it on a piece of paper but I need an algorithm that will be used for bigger data.