Find the distance between two nodes of a binary tree in Python
In this Answer, we'll learn how to calculate the distance between two nodes (
Approach
The above approach shows how to calculate the distance between nodes.
Here,
Example
For the above tree, we have to find the distance between node values
So,
So the distance between node values
Implementation
# 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)
Code explanation
Lines 8–28: The
root_to_Node_Pathmethod is defined to store the traversed nodes betweenrootand givenNodeinNodeslist.Lines 30–51: The
calculate_Distancemethod is defined to calculate the distance between two nodes (Node1andNode2).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
distancebetween two nodes.
Free Resources