Traverse tree to collect all children nodes, excluding unrelated branches-CodePudding

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.

CodePudding user response：

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]

CodePudding user response：

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]