In this Answer, we'll learn how to calculate the distance between two nodes (
The above approach shows how to calculate the distance between nodes.
Here,
For the above tree, we have to find the distance between node values
So,
So the distance between node values
# Node class for Treeclass Node:def __init__(self, value):self.value = valueself.right = Noneself.left = Nonedef root_to_Node_Path(root,Nodes, Node):if root is None:return False# Appending Node if treversed while reaching# to the desired nodeNodes.append(root.value)# check weather root is same as Nodeif root.value == Node :return True# Node is found in left or right sub treesif ((root.left != None and root_to_Node_Path(root.left, Nodes, Node)) or(root.right!= None and root_to_Node_Path(root.right, Nodes, Node))):return True# If Node does not exist in the treeNodes.pop()return Falsedef calculate_Distance(root, Node1, Node2):if root:# Store traversed nodes of Node1Nodes1 = []root_to_Node_Path(root, Nodes1, Node1)# Store traversed nodes of Node2Nodes2 = []root_to_Node_Path(root, Nodes2, Node2)# Iterating on both nodes treversed data# to find LCA (Lowest common Ancestor) distance from rootLCA=0while LCA<len(Nodes1) and LCA<len(Nodes2):if Nodes1[LCA] != Nodes2[LCA]:breakLCA = LCA+1# Calculating distance returningreturn (len(Nodes1)+len(Nodes2)-2*LCA)else:return 0# Generting treeroot = Node(5)root.left = Node(6)root.right = Node(7)root.left.left = Node(8)root.right.left = Node(9)root.right.right= Node(10)root.left.right = Node(11)root.right.left.right = Node(12)# Testing Code on examplesdistsnce = calculate_Distance(root, 8, 9)print ("Distance between nodes ", distsnce)distsnce = calculate_Distance(root, 12, 9)print ("Distance between nodes ", distsnce)
Lines 8–28: The root_to_Node_Path
method is defined to store the traversed nodes between root
and given Node
in Nodes
list.
Lines 30–51: The calculate_Distance
method is defined to calculate the distance between two nodes ( Node1
and Node2
).
Lines 42–46: Distance from root to LCA
(lowest common ancestor) is calculated using the stored traversed Nodes ( Nodes1
, Nodes2
).
Lines 54–61: The sample tree is created to test the code.
Lines 64–68: The code is tested against the created tree to calculate distance
between two nodes.
Free Resources