Python Program to Find the Nearest Common Ancestor in the Given set of Nodes
# Python Program To Find The Nearest Common Ancestors
# for a given Set of nodes
# The concept of Ancestors comes in tree especially being implemented in
# Binary Search Tree efficiently
# It can also be implemented in Binary Tree
# Here, Program for both types of trees will be given
# First of all, we'll define a Node
# It will work both for Binary Search and Binary Search Tree
# Defining a Node
class Node:
# Constructor to create a new Node
def __init__(self,key):
self.key=key
self.left=None
self.right=None
# Now , First we'll write code for Binary Search
# To Find the path from root node to given node of the tree,
# stores the path in a list path[], returns true if path
# exists otherwise returns false
def find_Path( root , path , k ):
# Returning False if the root is empty
if root is None:
return False
# Store this Node in the path list
path.append(root.key)
# If k is not in the path , it will be removed in the last
# line of fuction using pop()
# Check if the key is same as the Root
if root.key == k :
return True
# Check the presence of k in left or right sub-tree
if((root.left!=None and find_Path(root.left,path,k)) or (root.right!=None and find_Path(root.right,path,k))):
return True
# If k is not present in sub-tree , then remove
# the node of this sub-tree from the path and return false
path.pop()
return False
# End of function find_Path()
# Function To find Nearest Common Ancestors (NCA) or Lowest
# Common Ancestor(LCA) of two nodes n1 and n2
# Here , we consider all nodes as non-negative integers
# So, if any one of the node is not present in the Tree , then
# we return -1 as the flag value , otherwise return their NCA (or LCA)
# of the two nodes
def find_NCA( root , n1 , n2 ):
# First , we will store the path from root to n1 and n2 in path1 and path2
path1=[]
path2=[]
# To check the Presence of n1 and n2 node and Store their paths from root
if( not find_Path(root,path1,n1) or not find_Path(root,path2,n2)):
return -1
# Compare the path and find Nearest Common Ancestor
# It will be then farthest from the root
# So, the node before the first different value in the path is NCA
i=0 #For index of the path1 and path2
# To find the maximum limit of iteration
l = min( len(path1) , len(path2) )
while i<l :
if(path1[i]!=path2[i]): # To find first different node
break
i+=1
return path1[i-1] # As the first different node is at ith
# position , therefore NCA is at (i-1)th position
# Also , if in the iteration , the code do not encounter break
# Then it means one of the node is an ancestor of other
# So, return Statement is written outside of while loop take care of the same
# End of function find_NCA()
# To print NCA of given Nodes n1 and n2
def printNCA(root , n1 , n2 ):
nca = find_NCA(root , n1, n2 )
if(nca!=-1):
print("The Nearest Common Ancestor of %d and %d is %d" %(n1,n2,nca))
else:
print("Either of %d or %d or both does not exits in tree" %(n1,n2))
# End of printNCA() function
# Test Code for NCA in Binary Tree
# Let's create a binary tree in the given format:
# 2
# / \
# / \
# / \
# 4 6
# / \ / \
# / \ 9 8
# 5 7
# / \
# 1 3
root = Node(2)
root.left = Node(4)
root.right = Node(6)
root.left.left = Node(5)
root.left.right = Node(7)
root.right.left = Node(9)
root.right.right = Node(8)
root.left.left.left = Node(1)
root.left.left.right = Node(3)
# Printing the NCA of Two nodes
# Printing NCA for Program Defined Value
print("FOR PROGRAM-DEFINED IN BINARY TREE")
n1 = 4
n2 = 5
printNCA(root,n1,n2) # To find and print the NCA of node n1 and node n2
# From the diagram of Binary Tree , it is clear that NCA of 4 and 5 is 4 itself
#Therefore, the output will be:
#The Nearest Common Ancestor of 4 and 5 is 4
#Let's take another example
n1=10 # Notice 10 does not exists in the Tree
n2=9
printNCA(root,n1,n2)
# Since , n1 does not exists in the Tree , therefore the output will be:
# Either of 10 or 9 or both does not exits in tree
# Now for User-defined values
print("\n\nFOR USER-DEFINED IN BINARY TREE")
print("Enter two numbers from 1-9 to find their Nearest Common Ancestor :", sep= ' ')
# Exceptional Handling if value is not an Integer
while True:
try:
n1,n2= (int(x) for x in input().split())
break
except ValueError:
print("Please Enter two integers!" , sep= ' ')
printNCA(root,n1,n2)
# Print the NCA for node n1 and n2
# Or if n1 or n2 or both does not exists , then it prints the same
# END OF NEAREST COMMON ANCESTOR FOR BINARY TREE
# Now , let's start with Binary Search Tree ( or BST )
# BST is a special type of binary tree where the left node is less than the parent node and the right node is more than the parent node
# Since , BST is also a Binary Tree , So the above algorithm can be used to find Nearest Common Ancestor
# So, let's create a Binary Search Tree in the following Format:
# 6
# / \
# / \
# / \
# 4 8
# / \ / \
# / \ 7 9
# 2 5
# / \
# 1 3
root = Node(6)
root.left = Node(4)
root.right = Node(8)
root.left.left = Node(2)
root.left.right = Node(5)
root.right.left = Node(7)
root.right.right = Node(9)
root.left.left.left = Node(1)
root.left.left.right = Node(3)
# Printing the NCA of Two nodes
# Printing NCA for Program Defined Value
print("\n\nFOR PROGRAM-DEFINED IN BINARY SEARCH TREE USING find_NCA FUNCTION")
n1 = 4
n2 = 5
printNCA(root,n1,n2) # To find and print the NCA of node n1 and node n2
# From the diagram of Binary Tree , it is clear that NCA of 4 and 5 is 4 itself
#Therefore, the output will be:
#The Nearest Common Ancestor of 4 and 5 is 4
#Let's take another example
n1=10 # Notice 10 does not exists in the Tree
n2=9
printNCA(root,n1,n2)
# Since , n1 does not exists in the Tree , therefore the output will be:
# Either of 10 or 9 or both does not exits in tree
# Now for User-defined values
print("\n\nFOR USER-DEFINED IN BINARY SEARCH TREE USING find_NCA FUNCTION")
print("Enter two numbers from 1-9 to find their Nearest Common Ancestor :" , sep= ' ')
# Exceptional Handling if value is not an Integer
while True:
try:
n1,n2= (int(x) for x in input().split())
break
except ValueError:
print("Please Enter two integers!" , sep= ' ')
printNCA(root,n1,n2)
# Print the NCA for node n1 and n2
# Or if n1 or n2 or both does not exists , then it prints the same
# But the special property of Binary Search Tree helps us to optimize the Program
# So , here goes the optimized code to find Nearest Common Ancestor of BST
# Function to find Nearest Common Ancestor of nodes n1 and n2.
# But , Here we assume that both nodes n1 and n2 are present in tree
def BST_NCA(root, n1, n2):
# Returning None if the root is empty
if root is None:
return None
# If both nodes n1 and n2 are smaller than root, then NCA lies in left child
elif(root.key > n1 and root.key > n2):
return BST_NCA(root.left, n1, n2)
# If both nodes n1 and n2 are greater than root, then NCA lies in right child
elif(root.key < n1 and root.key < n2):
return BST_NCA(root.right, n1, n2)
# If the root lies between the nodes n1 and n2 , then this root is NCA
else:
return root
# END OF BST_NCA() FUNCTION
# Printing the NCA of Two nodes
# Printing NCA for Program Defined Value
# Binary Search Tree is already defined
# The structure is :
# 6
# / \
# / \
# / \
# 4 8
# / \ / \
# / \ 7 9
# 2 5
# / \
# 1 3
print("\n\nFOR PROGRAM-DEFINED IN BINARY SEARCH TREE USING BST_NCA FUNCTION")
n1 = 4
n2 = 5
nca=BST_NCA(root,n1,n2) # Compute NCA of n1 and n2 and store it in nca
# From the diagram of Binary Search Tree , it is clear that NCA of 4 and 5 is 4 itself
print("The Nearest Common Ancestor of %d and %d is %d" %(n1,n2,nca.key))
#Therefore, the output will be:
#The Nearest Common Ancestor of 4 and 5 is 4
# Now for User-defined values
print("\n\nFOR USER-DEFINED IN BINARY SEARCH TREE USING BST_NCA FUNCTION")
print("Enter two numbers from 1-9 to find their Nearest Common Ancestor :" , sep= ' ')
# Exceptional Handling if value is not an Integer
while True:
try:
n1,n2= (int(x) for x in input().split())
break
except ValueError:
print("Please Enter two integers!" , sep=' ')
nca=BST_NCA(root,n1,n2) # Compute NCA of n1 and n2 and store it in nca
print("The Nearest Common Ancestor of %d and %d is %d" %(n1,n2,nca.key))
# Print the NCA for node n1 and n2
# End of the program
# for a given Set of nodes
# The concept of Ancestors comes in tree especially being implemented in
# Binary Search Tree efficiently
# It can also be implemented in Binary Tree
# Here, Program for both types of trees will be given
# First of all, we'll define a Node
# It will work both for Binary Search and Binary Search Tree
# Defining a Node
class Node:
# Constructor to create a new Node
def __init__(self,key):
self.key=key
self.left=None
self.right=None
# Now , First we'll write code for Binary Search
# To Find the path from root node to given node of the tree,
# stores the path in a list path[], returns true if path
# exists otherwise returns false
def find_Path( root , path , k ):
# Returning False if the root is empty
if root is None:
return False
# Store this Node in the path list
path.append(root.key)
# If k is not in the path , it will be removed in the last
# line of fuction using pop()
# Check if the key is same as the Root
if root.key == k :
return True
# Check the presence of k in left or right sub-tree
if((root.left!=None and find_Path(root.left,path,k)) or (root.right!=None and find_Path(root.right,path,k))):
return True
# If k is not present in sub-tree , then remove
# the node of this sub-tree from the path and return false
path.pop()
return False
# End of function find_Path()
# Function To find Nearest Common Ancestors (NCA) or Lowest
# Common Ancestor(LCA) of two nodes n1 and n2
# Here , we consider all nodes as non-negative integers
# So, if any one of the node is not present in the Tree , then
# we return -1 as the flag value , otherwise return their NCA (or LCA)
# of the two nodes
def find_NCA( root , n1 , n2 ):
# First , we will store the path from root to n1 and n2 in path1 and path2
path1=[]
path2=[]
# To check the Presence of n1 and n2 node and Store their paths from root
if( not find_Path(root,path1,n1) or not find_Path(root,path2,n2)):
return -1
# Compare the path and find Nearest Common Ancestor
# It will be then farthest from the root
# So, the node before the first different value in the path is NCA
i=0 #For index of the path1 and path2
# To find the maximum limit of iteration
l = min( len(path1) , len(path2) )
while i<l :
if(path1[i]!=path2[i]): # To find first different node
break
i+=1
return path1[i-1] # As the first different node is at ith
# position , therefore NCA is at (i-1)th position
# Also , if in the iteration , the code do not encounter break
# Then it means one of the node is an ancestor of other
# So, return Statement is written outside of while loop take care of the same
# End of function find_NCA()
# To print NCA of given Nodes n1 and n2
def printNCA(root , n1 , n2 ):
nca = find_NCA(root , n1, n2 )
if(nca!=-1):
print("The Nearest Common Ancestor of %d and %d is %d" %(n1,n2,nca))
else:
print("Either of %d or %d or both does not exits in tree" %(n1,n2))
# End of printNCA() function
# Test Code for NCA in Binary Tree
# Let's create a binary tree in the given format:
# 2
# / \
# / \
# / \
# 4 6
# / \ / \
# / \ 9 8
# 5 7
# / \
# 1 3
root = Node(2)
root.left = Node(4)
root.right = Node(6)
root.left.left = Node(5)
root.left.right = Node(7)
root.right.left = Node(9)
root.right.right = Node(8)
root.left.left.left = Node(1)
root.left.left.right = Node(3)
# Printing the NCA of Two nodes
# Printing NCA for Program Defined Value
print("FOR PROGRAM-DEFINED IN BINARY TREE")
n1 = 4
n2 = 5
printNCA(root,n1,n2) # To find and print the NCA of node n1 and node n2
# From the diagram of Binary Tree , it is clear that NCA of 4 and 5 is 4 itself
#Therefore, the output will be:
#The Nearest Common Ancestor of 4 and 5 is 4
#Let's take another example
n1=10 # Notice 10 does not exists in the Tree
n2=9
printNCA(root,n1,n2)
# Since , n1 does not exists in the Tree , therefore the output will be:
# Either of 10 or 9 or both does not exits in tree
# Now for User-defined values
print("\n\nFOR USER-DEFINED IN BINARY TREE")
print("Enter two numbers from 1-9 to find their Nearest Common Ancestor :", sep= ' ')
# Exceptional Handling if value is not an Integer
while True:
try:
n1,n2= (int(x) for x in input().split())
break
except ValueError:
print("Please Enter two integers!" , sep= ' ')
printNCA(root,n1,n2)
# Print the NCA for node n1 and n2
# Or if n1 or n2 or both does not exists , then it prints the same
# END OF NEAREST COMMON ANCESTOR FOR BINARY TREE
# Now , let's start with Binary Search Tree ( or BST )
# BST is a special type of binary tree where the left node is less than the parent node and the right node is more than the parent node
# Since , BST is also a Binary Tree , So the above algorithm can be used to find Nearest Common Ancestor
# So, let's create a Binary Search Tree in the following Format:
# 6
# / \
# / \
# / \
# 4 8
# / \ / \
# / \ 7 9
# 2 5
# / \
# 1 3
root = Node(6)
root.left = Node(4)
root.right = Node(8)
root.left.left = Node(2)
root.left.right = Node(5)
root.right.left = Node(7)
root.right.right = Node(9)
root.left.left.left = Node(1)
root.left.left.right = Node(3)
# Printing the NCA of Two nodes
# Printing NCA for Program Defined Value
print("\n\nFOR PROGRAM-DEFINED IN BINARY SEARCH TREE USING find_NCA FUNCTION")
n1 = 4
n2 = 5
printNCA(root,n1,n2) # To find and print the NCA of node n1 and node n2
# From the diagram of Binary Tree , it is clear that NCA of 4 and 5 is 4 itself
#Therefore, the output will be:
#The Nearest Common Ancestor of 4 and 5 is 4
#Let's take another example
n1=10 # Notice 10 does not exists in the Tree
n2=9
printNCA(root,n1,n2)
# Since , n1 does not exists in the Tree , therefore the output will be:
# Either of 10 or 9 or both does not exits in tree
# Now for User-defined values
print("\n\nFOR USER-DEFINED IN BINARY SEARCH TREE USING find_NCA FUNCTION")
print("Enter two numbers from 1-9 to find their Nearest Common Ancestor :" , sep= ' ')
# Exceptional Handling if value is not an Integer
while True:
try:
n1,n2= (int(x) for x in input().split())
break
except ValueError:
print("Please Enter two integers!" , sep= ' ')
printNCA(root,n1,n2)
# Print the NCA for node n1 and n2
# Or if n1 or n2 or both does not exists , then it prints the same
# But the special property of Binary Search Tree helps us to optimize the Program
# So , here goes the optimized code to find Nearest Common Ancestor of BST
# Function to find Nearest Common Ancestor of nodes n1 and n2.
# But , Here we assume that both nodes n1 and n2 are present in tree
def BST_NCA(root, n1, n2):
# Returning None if the root is empty
if root is None:
return None
# If both nodes n1 and n2 are smaller than root, then NCA lies in left child
elif(root.key > n1 and root.key > n2):
return BST_NCA(root.left, n1, n2)
# If both nodes n1 and n2 are greater than root, then NCA lies in right child
elif(root.key < n1 and root.key < n2):
return BST_NCA(root.right, n1, n2)
# If the root lies between the nodes n1 and n2 , then this root is NCA
else:
return root
# END OF BST_NCA() FUNCTION
# Printing the NCA of Two nodes
# Printing NCA for Program Defined Value
# Binary Search Tree is already defined
# The structure is :
# 6
# / \
# / \
# / \
# 4 8
# / \ / \
# / \ 7 9
# 2 5
# / \
# 1 3
print("\n\nFOR PROGRAM-DEFINED IN BINARY SEARCH TREE USING BST_NCA FUNCTION")
n1 = 4
n2 = 5
nca=BST_NCA(root,n1,n2) # Compute NCA of n1 and n2 and store it in nca
# From the diagram of Binary Search Tree , it is clear that NCA of 4 and 5 is 4 itself
print("The Nearest Common Ancestor of %d and %d is %d" %(n1,n2,nca.key))
#Therefore, the output will be:
#The Nearest Common Ancestor of 4 and 5 is 4
# Now for User-defined values
print("\n\nFOR USER-DEFINED IN BINARY SEARCH TREE USING BST_NCA FUNCTION")
print("Enter two numbers from 1-9 to find their Nearest Common Ancestor :" , sep= ' ')
# Exceptional Handling if value is not an Integer
while True:
try:
n1,n2= (int(x) for x in input().split())
break
except ValueError:
print("Please Enter two integers!" , sep=' ')
nca=BST_NCA(root,n1,n2) # Compute NCA of n1 and n2 and store it in nca
print("The Nearest Common Ancestor of %d and %d is %d" %(n1,n2,nca.key))
# Print the NCA for node n1 and n2
# End of the program
More Articles of Arman Agarwal:
| Name | Views | Likes |
|---|---|---|
| Python Program to Find the Nearest Common Ancestor in the Given set of Nodes | 351 | 1 |
| Introduction To SQLite3 in Python | 423 | 2 |
| Python SQLITE3 connect Object | 260 | 0 |
Comments