Closed afrooze closed 2 years ago
I used the node predecessor
to iterate over the tree nodes, starting from the leaf to the root:
node = tree.get_node(node_id)
while node.predecessor:
if your_condition:
return node.identifier
node = tree[node.predecessor]
An alternative answer to @yuvalshi0 is:
Execution time will depend on the depth of desired nodes. There are better alternatives out there. Search lower common ancestor graph as a start.
Example function
def get_common_frame(tree, node_1: str, node_2: str) -> str:
"""gets the lowest common ancester between two nodes.
Args:
tree: treelib tree object
node_1 (str): the ID of the first node (first and second has no meaning)
node_2 (str): the ID of the second node
Returns:
str: the identifier of the lowest common ancestor node
"""
# check to see which node is deeper
if tree.depth(node_1) > tree.depth(node_1):
# node 1 is further down tree
lower_node = node_1
higher_node = node_2
else:
# node 2 is further down tree
lower_node = node_2
higher_node = node_1
# go until lower node has same depth as higher node
while tree.depth(lower_node) != tree.depth(higher_node):
lower_node = tree.parent(lower_node).identifier
# move both up one level until lower node equals higher node
while lower_node != higher_node:
lower_node = tree.parent(lower_node).identifier
higher_node = tree.parent(higher_node).identifier
# return
return lower_node
Edited: To improve clarity
thanks for answers
Hi. can you explain to me how can find a common parent for each node?