Python Program to Find the Nearest Common Ancestor in the Given set of Nodes

Suppose we have a binary tree, so
the least common ancestor of the

i)               node 9 and node 6    =>    node 1

ii)              node 5 and node 9    =>    node 5

iii)            node 4 and node 6    =>    node 7

Definition of Nearest Common Ancestor

Let T be a binary tree. Let u and v be the nodes. The lowest common ancestor between two nodes u and v is defined as the lowest node In T that has both u and v as descendants. The Lca is the shared ancestor of u and v.

ALGORITHM

1.) If (node found)

       return node

     else

       return Null

 2.) Traverse the nodes in Binary Tree using the inorder traversal i.e left -> parent ->   right node

      Again follow step 1

 3.) If the both node returns not null then it is the lowest common ancestor

      If at least one node returns Null then still we haven%u2019t got lowest common ancestor

The third point can be described using the below diagram:-

class Node: 

    def __init__(self,data): 

    #Assign data to the new node, set left and right children to None 

        self.data = data; 

        self.left = None; 

        self.right = None; 

def lowestCommonAncestor(root,n1,n2):        # Here, root represents the parent node

    # Step 1

    if(root is None):

        return None

    if(root.data == n1 or root.data==n2):

        return root

      # Step 2

    left = lowestCommonAncestor(root.left,n1,n2)

    right = lowestCommonAncestor(root.right,n1,n2)

     # Step 3 

    if left and right:     # Both nodes return some value, then we have got the lca [ where root is lca ]

        return root

     if left:                    # If one node returned NULL

         return left

     else:

         return right

   

root = Node(11); 

root.left = Node(12); 

root.right = Node(13); 

root.left.left = Node(14); 

root.left.right = Node(45); 

root.right.left = Node(64); 

root.right.right = Node(73);

print(lowestCommonAncestor(root,64,12).data) 

Output :- 13