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 (Node1Node1 and Node2Node2) of a binary tree. To find the distance between two nodes, the distance is the number of nodes to be traversed from Node1Node1 to Node2Node2.

Approach

The above approach shows how to calculate the distance between nodes.

Here, Node1Node1 and Node2Node2 represent the nodes we want to find the distance between. Additionally, rootroot is the top node of the tree and LCALCA is the lowest common ancestor between the two nodes.

Example

%0 node_1 5 node_2 6 node_1->node_2 node_3 7 node_1->node_3 node_1666855303326 8 node_2->node_1666855303326 node_1666855328302 9 node_2->node_1666855328302 node_1666855353235 10 node_3->node_1666855353235 node_1666855344749 11 node_3->node_1666855344749 node_1666855295824 12 node_1666855353235->node_1666855295824
Binary tree

For the above tree, we have to find the distance between node values 99 and 1111. We'll use the proposed approach.

So,

So the distance between node values 99 and 1111 is 44 because we have to traverse 44 nodes.

Implementation

# Node class for Tree
class Node:
def __init__(self, value):
self.value = value
self.right = None
self.left = None
def root_to_Node_Path(root,Nodes, Node):
if root is None:
return False
# Appending Node if treversed while reaching
# to the desired node
Nodes.append(root.value)
# check weather root is same as Node
if root.value == Node :
return True
# Node is found in left or right sub trees
if ((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 tree
Nodes.pop()
return False
def calculate_Distance(root, Node1, Node2):
if root:
# Store traversed nodes of Node1
Nodes1 = []
root_to_Node_Path(root, Nodes1, Node1)
# Store traversed nodes of Node2
Nodes2 = []
root_to_Node_Path(root, Nodes2, Node2)
# Iterating on both nodes treversed data
# to find LCA (Lowest common Ancestor) distance from root
LCA=0
while LCA<len(Nodes1) and LCA<len(Nodes2):
if Nodes1[LCA] != Nodes2[LCA]:
break
LCA = LCA+1
# Calculating distance returning
return (len(Nodes1)+len(Nodes2)-2*LCA)
else:
return 0
# Generting tree
root = 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 examples
distsnce = 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_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

Copyright ©2025 Educative, Inc. All rights reserved