# 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

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