solution for tree traversal with python

Question

I am handling with a new problem that relates to tree traverse methods. I have a binary tree with conditional search option. I want to parse an input of type string and traverse tree based on this parsed string. the conditions are a bit complicated so let me explain it using an example:

input :

data = [
'dummy',
['null', 'd2', 'd1'],
['null', 'b2', 'b1'],
'dummy',
['b2', 'a2', 'a1'],
['b1', 'c1', 'c2'],
'dummy',
'dummy',
'dummy',
'dummy',
['c1', 'a1', 'a2'],
['c2', 'a2', 'a1']
]

The output should be:

d2,b2,a2
d2,b2,a1
d1,b2,a2
d1,b2,a1

d2,b1,c1,a1
d2,b1,c1,a2
d1,b1,c1,a1
d1,b1,c1,a2

d2,b1,c2,a2
d2,b1,c2,a1
d1,b1,c2,a2
d1,b1,c2,a1

And that's the picture of the tree:

These are my codes that only display the first output line:

solution, solutions = [], []

for d in data:
    x = d[0] * 2
    child = []
    for i in data:
        if i[0] == x:
            child.append(i[0])
        if i[0] == x + 1:
            child.append(i[0])
    d.insert(1, child)

root = data[1]
solution.append(root[3])
i = 0
pointer = data[root[0] * 2]
last = None
while i <= len(data):
    if solution[-1:] != [last]:
        solution.append(pointer[3])
    try:
        pointer = data[pointer[0] * 2]
    except:
        break
    if len(pointer) > 3:
        if pointer[2] == 'null' or pointer[2] == solution[-1:]:
            solution.append(pointer[3])
    else:
        solutions.append(solution)
        solution = []
        pointer = data[int((pointer[0] / 2) + 1)]

    last = pointer[3]
    i += 1
print(solutions)

This is the output :

[['d2', 'b2', 'a2']]

More details:

This tree is lexicographic preference tree and i implement it with array. I suppose that each node of tree may have 2 children or less and each edge may have conditional or not.

Now, i want to find the solution of tree. For finding solution, i have to trase the tree

I explain the parameter of tree and array with example:

Answer 1

I think the following implementation should do it. It produces the output for the example data you have provided. I believe there is some redundancy in that data structure, so I have added some validation in the code as well, and if it violates that validation, an error is raised.

def getpaths(data, i, tracks):
    paths = []
    isleaf = True
    j = 2*i
    for k in range(1, 3):
        if j < len(data) and data[j] != 'dummy':
            isleaf = False
            if data[j][0] == 'null':
                yield from getpaths(data, j, [track + [data[i][m]] for track in tracks for m in range(1,3)])
                break
            elif data[j][0] != data[i][k]:
                raise ValueError("inconsistent tree")
            else:
                yield from getpaths(data, j, [track + [data[i][k]] for track in tracks])
                j += 1
    if isleaf:
        for track in tracks:
            yield track + [data[i][1]]
            yield track + [data[i][2]]

# Example run
data = [
    'dummy',
    ['null', 'd2', 'd1'],
    ['null', 'b2', 'b1'],
    'dummy',
    ['b2', 'a2', 'a1'],
    ['b1', 'c1', 'c2'],
    'dummy',
    'dummy',
    'dummy',
    'dummy',
    ['c1', 'a1', 'a2'],
    ['c2', 'a2', 'a1']
]

for path in getpaths(data, 1, [[]]):
    print(path)