CODEWITHSUNDEEP
pythondepth-first-searchtree-traversal
Apostolos
Apostolos

Reputation: 8121

Get paths of a tree but with all leaves o a node in one path in python

I have the following Node object

class Node(object):
    def __init__(parent=None, data)
        self.__parent = parent
        self.__data = data
        self.__children = []

   # parent and data properties getters and setters are left out for convinience

   def add_node(self, node):
       node.parent = self
       self.__children.append(node)

so I have a tree that looks like this 

            dummy_root(nodata)
             /         |      \
            A          B       C              
          /   \      /   \   /   \
         D     E    F    G   H    I 
        / \   / \  / \  / \ / \  / \
       K   L M  N O  P Q  R S  T U  V

I want to get all paths for all children of dummy_root. The tricky part that have not been able to figure out yet is that the leaf nodes need to belong to one path, e.g

paths = [
            [A, D, K, L], 
            [A, E, M, N], 
            [B, F, O, P], 
            [B, G, Q, R],
            [C, H, S, T], 
            [C, I, U, V]
]

I have found a way to get all paths but what I get is different paths for each leaf e.g

[A, D, K] and [A, D, L]

Python code:

 def __find_paths_recursive(node, path):
    path = deepcopy(path)
    path.append(node.data)
    if not node.children:
        pathss.append(path)
    for child in node.children:
        self.__find_paths_recursive(child, path)

for child in dummy_root.children:
    path = []
    find_paths_recursive(child, path)

Upvotes: 1

Views: 386

Answers (2)

Gennady Kandaurov
Gennady Kandaurov

Reputation: 1964

You can add one iteration over your result paths with groupby

result = []
for prefix, paths_iter in groupby(paths, key=lambda x: x[:-1]):
    result.append(prefix + [lst[-1] for lst in val])

print(result)
[[A, D, K, L],
 [A, E, M, N], 
 [B, F, O, P], 
 [B, G, Q, R],
 [C, H, S, T], 
 [C, I, U, V]]

Another way is to check if children are leafs during node processing:

def __find_paths_recursive(node, path):
    path = deepcopy(path)
    path.append(node.data)
    if not node.children:
        return
    if node.children[0].children:  # children are not leafs
        for child in node.children:
            self.__find_paths_recursive(child, path)
    else:
        path.extend(node.children)  # since all children are leafs
        paths.append(path)

Upvotes: 1

themistoklik
themistoklik

Reputation: 880

I am still not sure if I'm getting this correctly, if not let me know

To go from [A,D,K] and [A,D,L] to [A,D,K,L], you can make them into OrderedSets and get their union.

You could add this step each time you're done processing leaf nodes.

Alternatively you can do a preorder traversal for every child of your root node.

Upvotes: 0

Related Questions