Traverse tree to collect all children nodes, excluding unrelated branches

user_17135505 0
Viewed 334

I have a list of child-parent tuples. I would like to traverse through the tree to collect all the children for input node.

in_list = [(2,1),(3,2),(4,3),(6,5),(7,4),(8,4)]

Say now I would like to collect all children for node 2. That would be

out_list = [3,4,7,8]

Does this problem or its solution have any specific name? Just need to know where to look.

traversal tree algorithm python
2 Answers

You need to traverse these nodes in in_list like DFS, You can try this:

def DFS(path, lst, father):
    for (a,b) in lst:
        if b == father:
            path.append(a)
            DFS(path, lst, a)
    return path

in_list = [(2,1),(3,2),(4,3),(6,5),(7,4),(8,4)]
res = DFS([], in_list , 2)
print(res)

Output:

[3, 4, 7, 8]
user_17405770

You can use a recursive generator function:

in_list = [(2,1),(3,2),(4,3),(6,5),(7,4),(8,4)]
def paths(n, c = []):
   if not (t:=[a for a, b in in_list if b == n]):
      yield from (c + [n])
   else:
      yield from [j for k in t for j in paths(k, c+[n])]

print([*set(paths(2))][1:])

Output:

[3, 4, 7, 8]
user_73267380
Related