BPL BPL -4 years ago 120
Python Question

How can I get a list of tree-ancestors from a particular node?

Given a tree where each node can have N children but only 1 parent. How can I get the ancestors of one node? For instance, let's say i got this tree:

# Operator
# ... FooOperator
# ...... BOperator
# ......... B1Operator
# ............ B11Operator
# ...... AOperator
# ......... A2Operator
# ......... A1Operator
# ......... A3Operator
# ...... COperator
# ......... C1Operator
# ......... C2Operator
# ............ C21Operator

tree = {
'children': [{
'children': [{
'children': [{
'children': [{
'children': [],
'class': 'B11Operator',
'parent': 'B1Operator'
}],
'class': 'B1Operator',
'parent': 'BOperator'
}],
'class': 'BOperator',
'parent': 'FooOperator'
},{
'children': [{
'children': [],
'class': 'A2Operator',
'parent': 'AOperator'
},{
'children': [],
'class': 'A1Operator',
'parent': 'AOperator'
},{
'children': [],
'class': 'A3Operator',
'parent': 'AOperator'
}],
'class': 'AOperator',
'parent': 'FooOperator'},{
'children': [{
'children': [],
'class': 'C1Operator',
'parent': 'COperator'
},{
'children': [{
'children': [],
'class': 'C21Operator',
'parent': 'C2Operator'
}],
'class': 'C2Operator',
'parent': 'COperator'
}],
'class': 'COperator',
'parent': 'FooOperator'
}],
'class': 'FooOperator',
'parent': 'Operator'
}],
'class': 'Operator',
'parent': None
}

def display_tree(node, indent=0):
print('.' * indent, node['class'])
indent += 3
for child in node['children']:
display_tree(child, indent)

display_tree(tree)


How would you get an ancestors-list from
"C21Operator"
such as the result was
["Operator", "FooOperator", "COperator", "C2Operator", "C21Operator"]
?

Answer Source

Given your data structure, I think only a brute-force solution is possible:

In [6]: def path_to_child(tree, target, acc=None):
   ...:     if acc is None:
   ...:         acc = []
   ...:     if tree['class'] == target:
   ...:         return acc
   ...:     for child in tree['children']:
   ...:         found = path_to_child(child, target, acc + [tree['class']])
   ...:         if found is not None:
   ...:             return found
   ...:

In [7]: path_to_child(tree, 'C21Operator')
Out[7]: ['Operator', 'FooOperator', 'COperator', 'C2Operator']

In [8]:

You can perhaps traverse the tree more intelligently if you know where to expect your target.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download