Lowest Common Ancestor in a Binary Tree | Set 1 | A binary tree node ; This function returns pointer to LCA of two given values n1 and n2 This function assumes that n1 and n2 are present in Binary Tree ; Base Case ; If either n1 or n2 matches with root 's key, report  the presence by returning root (Note that if a key is  ancestor of other, then the ancestor key becomes LCA ; Look for keys in left and right subtrees ; If both of the above calls return Non - NULL , then one key is present in once subtree and other is present in other , So this node is the LCA ; Otherwise check if left subtree or right subtree is LCA ; Driver program to test above function Let us create a binary tree given in the above example
class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def findLCA ( root , n1 , n2 ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return None NEW_LINE DEDENT if root . key == n1 or root . key == n2 : NEW_LINE INDENT return root NEW_LINE DEDENT left_lca = findLCA ( root . left , n1 , n2 ) NEW_LINE right_lca = findLCA ( root . right , n1 , n2 ) NEW_LINE if left_lca and right_lca : NEW_LINE INDENT return root NEW_LINE DEDENT return left_lca if left_lca is not None else right_lca NEW_LINE DEDENT root = Node ( 1 ) NEW_LINE root . left = Node ( 2 ) NEW_LINE root . right = Node ( 3 ) NEW_LINE root . left . left = Node ( 4 ) NEW_LINE root . left . right = Node ( 5 ) NEW_LINE root . right . left = Node ( 6 ) NEW_LINE root . right . right = Node ( 7 ) NEW_LINE print " LCA ( 4,5 ) ▁ = ▁ " , findLCA ( root , 4 , 5 ) . key NEW_LINE print " LCA ( 4,6 ) ▁ = ▁ " , findLCA ( root , 4 , 6 ) . key NEW_LINE print " LCA ( 3,4 ) ▁ = ▁ " , findLCA ( root , 3 , 4 ) . key NEW_LINE print " LCA ( 2,4 ) ▁ = ▁ " , findLCA ( root , 2 , 4 ) . key NEW_LINE