Least common ancestor (LCA) is an extremely useful algorithm in taxonomy assignment which enables the identification of the shared parent node for a list of given child nodes. Here is a piece of code implementing the LCA search based on nested dictionary in Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | # define the tree example_dict = {'key1a': {}, 'key1b': {}, 'key1c': {'key2a': {'key3a': {}}, 'key2b': {'key3b': {}}, 'key2c': {}, 'key2d': {}, 'key2e': {'key3c': {'key4a': {'key5a': {'key6a': {}}, 'key5b': {} } } } } } # recursive def locate_node(tree, node): for child_key, child_value in tree.items(): if isinstance(child_value, dict): result = locate_node(child_value, node) if result: return [child_key] + result if child_key == node: return([child_key]) node = locate_node(example_dict, 'key5b') print(node) |