Posted on by Kalkicode
Code Binary Tree

Lowest common ancestor of a binary tree in python

Python program for Lowest common ancestor of a binary tree. Here more information.

#  Python 3 program for
#  Find lowest common ancestor in a binary tree

#  Binary Tree Node
class TreeNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	def __init__(self) :
		self.root = None
	
	#  Find given node value exist or not
	def findNode(self, node, value) :
		if (node != None) :
			if (node.data == value) :
				return True
			else :
				return (self.findNode(node.left, value) or 
                        self.findNode(node.right, value))
			
		
		return False
	
	#  This function are finding the LCA of given two  node
	def lca(self, node, x, y) :
		if (node != None) :
			if (node.data == x or node.data == y) :
				#  When tree node data is equal to x or value y
				return node
			
			#  Find lca in left and right subtree
			first = self.lca(node.left, x, y)
			second = self.lca(node.right, x, y)
			if (first != None and second != None) :
				#  When first and second subtree contains node values
				#  This condition is based on post order
				#  traversal so current node is resultant of LCA initial
				return node
			
			if (first != None) :
				#  When first subtree contains result
				return first
			
			#  return the result of second subtree
			return second
		else :
			#  When tree node are empty
			return None
		
	
	#  This function are handle the request of
	#  find LCA of two tree nodes
	def findLCA(self, x, y) :
		#  Display node value
		print("\nNodes [", x ,", ", y ,"] ")
		a = self.findNode(self.root, x)
		b = self.findNode(self.root, y)
		if (a and b) :
			#  Case A
			#  When both node value exist
			result = self.lca(self.root, x, y)
			if (result != None) :
				print("LCA : ", result.data)
			else :
				print("None")
			
		elif (a == True) :
			#  Case B
			#  When x value in exist but y are missing
			print("Node value ", y ," are missing")
		elif (b == True) :
			#  Case C
			#  When y value in exist but x are missing
			print("Node value ", x ," are missing")
		else :
			#  Case D
			#  When both are missing
			print("Pair are missing")
		
	

def main() :
	#  Make a new Binary Tree
	tree = BinaryTree()
	# Make A Binary Tree
	#  -----------------------
	#          1
	#         /  \
	#        2    3
	#       /    /  \
	#      4    5    6
	#       \       /
	#        7     8
	#  Binary tree nodes
	tree.root = TreeNode(1)
	tree.root.left = TreeNode(2)
	tree.root.right = TreeNode(3)
	tree.root.right.right = TreeNode(6)
	tree.root.right.left = TreeNode(5)
	tree.root.left.left = TreeNode(4)
	tree.root.left.left.right = TreeNode(7)
	tree.root.right.right.left = TreeNode(8)
	#  Test case
	tree.findLCA(8, 5)
	tree.findLCA(7, 2)
	tree.findLCA(7, 8)
	tree.findLCA(3, 7)
	tree.findLCA(15, 4)
	tree.findLCA(7, 9)
	tree.findLCA(11, 9)
	tree.findLCA(5, 5)

if __name__ == "__main__": main()

Output

Nodes [ 8 ,  5 ]
LCA :  3

Nodes [ 7 ,  2 ]
LCA :  2

Nodes [ 7 ,  8 ]
LCA :  1

Nodes [ 3 ,  7 ]
LCA :  1

Nodes [ 15 ,  4 ]
Node value  15  are missing

Nodes [ 7 ,  9 ]
Node value  9  are missing

Nodes [ 11 ,  9 ]
Pair are missing

Nodes [ 5 ,  5 ]
LCA :  5

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment