Python program to find distance between two nodes of a binary tree.














































Python program to find distance between two nodes of a binary tree.



Description:

Distance between two nodes is the minimum number of edges to be traversed to reach one node from other.



Dist(4,5)=2
Dist(4,6)=4
Dist(3,4)=3
Dist(2,4)=1
Dist(8,5)=5


Program:

class Node: def __init__(self, data): self.data = data self.right = None self.left = None def pathToNode(root, path, k): # base case handling if root is None: return False # append the node value in path path.append(root.data) # See if the k is same as root's data if root.data == k : return True # Check if k is found in left or right # sub-tree if ((root.left != None and pathToNode(root.left, path, k)) or (root.right!= None and pathToNode(root.right, path, k))): return True # If not present in subtree rooted with root, # remove root from path and return False path.pop() return False def distance(root, data1, data2): if root: # store path corresponding to node: data1 path1 = [] pathToNode(root, path1, data1) # store path corresponding to node: data2 path2 = [] pathToNode(root, path2, data2) # iterate through the paths to find the # common path length i=0 while i<len(path1) and i<len(path2): # get out as soon as the path differs # or any path's length get exhausted if path1[i] != path2[i]: break i = i+1 # get the path length by deducting the # intersecting path length (or till LCA) return (len(path1)+len(path2)-2*i) else: return 0 # Driver Code to test above functions root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.right.right= Node(7) root.right.left = Node(6) root.left.right = Node(5) root.right.left.right = Node(8) dist = distance(root, 4, 5) print ("Distance between node {} & {}: {}".format(4, 5, dist) ) dist = distance(root, 4, 6) print( "Distance between node {} & {}: {}".format(4, 6, dist) ) dist = distance(root, 3, 4) print ("Distance between node {} & {}: {}".format(3, 4, dist) ) dist = distance(root, 2, 4) print ("Distance between node {} & {}: {}".format(2, 4, dist) ) dist = distance(root, 8, 5) print ("Distance between node {} & {}: {}".format(8, 5, dist) )


Output:

Distance between node 4 & 5: 2
Distance between node 4 & 6: 4
Distance between node 3 & 4: 3
Distance between node 2 & 4: 1
Distance between node 8 & 5: 5
>>> 


More Articles of Khushboo Singh:

Name Views Likes
Python program to insert an element in binary tree. 807 20
Tokenize text using NLTK in Python. 1183 12
Python Remove multiple elements from list while Iterating. 722 22
Python How to Check if an item exists in list ? 4251 14
Python How to remove multiple elements from list ? 729 26
Python program to check if two trees are mirror of each other without using recursion. 654 19
Python program to find maximum in Binary tree. 922 19
Python Check if all elements are same using Set 700 15
Python program to find diameter of a binary tree. 1072 20
Python program to print root to leaf paths without using recursion. 827 20
Python program to find root of the tree where children id sum for every node is given. 666 23
Introduction of Python NLTK library 1340 25
Categorizing and Tagging Sentences using NLTK in Python . 991 19
Python program to find height of a tree without using recursion. 654 16
Python program to find sum of all nodes of the given perfect binary tree. 646 19
Python program to find minimum in binary tree. 807 23
Python Check if element exist in list using list.count() function. 681 13
Python program to convert a given binary tree to doubly linked list. 876 20
Python program to find distance between two nodes of a binary tree. 1507 20
NLTK stop Words 1085 13
Python program to find largest binary search tree in a Binary Tree. 925 20
Python program to find inorder successor in binary search tree with recursion. 1196 18
Python program to convert a binary tree into doubly linked list in spiral fashion. 786 15
Python List check if element are same using all() 660 12
Python program to check if two trees are identical using recursion. 700 30
Python Find the occurrence count of an element in the tuple using count() 954 23
Python Convert two lists to a dictionary 717 19
Python program to construct a complete binary tree from given array. 1411 14
Python program to find diameter of binary tree in O(n). 863 17
Introduction to the AVL tree. 734 15
Python program to check if two trees are identical without using recursion 650 17
Python Convert a list of tuples to dictionary. 1070 24
Python program to convert a binary tree to a circular doubly link list. 640 21
Python Check if element exist in list based on own logic. 729 23
Python program to merge two binary trees by doing node sum using recursion 989 27
Python program to check whether a given binary tree is perfect or not. 670 17
Python Check if all elements are same using list.count(). 1078 28
Python program to find an element into binary tree 620 12
Python program to find lowest common ancestor in a binary tree 1201 24

Comments