Suppose we have a binary tree, so

the least common ancestor of the

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