### 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