Lowest Common Ancestor in a Binary Tree | Set 1 | A binary tree node ; This function retturn pointer to LCA of two given values n1 and n2 v1 is set as true by this function if n1 is found v2 is set as true by this function if n2 is found ; Base Case ; IF either n1 or n2 matches ith root 's key, report  the presence by setting v1 or v2 as true and return  root (Note that if a key is ancestor of other, then the ancestor key becomes LCA) ; Look for keys in left and right subtree ; 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 ; Returns true if key k is present in tree rooted with root ; This function returns LCA of n1 and n2 onlue if both n1 and n2 are present in tree , otherwise returns None ; Initialize n1 and n2 as not visited ; Find lac of n1 and n2 using the technique discussed above ; Returns LCA only if both n1 and n2 are present in tree ; Else return None ; Driver program to test above function
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 findLCAUtil ( root , n1 , n2 , v ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return None NEW_LINE DEDENT if root . key == n1 : NEW_LINE INDENT v [ 0 ] = True NEW_LINE return root NEW_LINE DEDENT if root . key == n2 : NEW_LINE INDENT v [ 1 ] = True NEW_LINE return root NEW_LINE DEDENT left_lca = findLCAUtil ( root . left , n1 , n2 , v ) NEW_LINE right_lca = findLCAUtil ( root . right , n1 , n2 , v ) 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 def find ( root , k ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return False NEW_LINE DEDENT if ( root . key == k or find ( root . left , k ) or find ( root . right , k ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def findLCA ( root , n1 , n2 ) : NEW_LINE INDENT v = [ False , False ] NEW_LINE lca = findLCAUtil ( root , n1 , n2 , v ) NEW_LINE if ( v [ 0 ] and v [ 1 ] or v [ 0 ] and find ( lca , n2 ) or v [ 1 ] and find ( lca , n1 ) ) : NEW_LINE INDENT return lca NEW_LINE DEDENT return None 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 lca = findLCA ( root , 4 , 5 ) NEW_LINE if lca is not None : NEW_LINE INDENT print " LCA ( 4 , ▁ 5 ) ▁ = ▁ " , lca . key NEW_LINE DEDENT else : NEW_LINE INDENT print " Keys ▁ are ▁ not ▁ present " NEW_LINE DEDENT lca = findLCA ( root , 4 , 10 ) NEW_LINE if lca is not None : NEW_LINE INDENT print " LCA ( 4,10 ) ▁ = ▁ " , lca . key NEW_LINE DEDENT else : NEW_LINE INDENT print " Keys ▁ are ▁ not ▁ present " NEW_LINE DEDENT