Lowest Common Ancestor in a Binary Search Tree . | A recursive python program to find LCA of two nodes n1 and n2 A Binary tree node ; Function to find LCA of n1 and n2 . The function assumes that both n1 and n2 are present in BST ; If both n1 and n2 are smaller than root , then LCA lies in left ; If both n1 and n2 are greater than root , then LCA lies in right ; Let us construct the BST shown in the figure
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def lca ( root , n1 , n2 ) : NEW_LINE INDENT while root : NEW_LINE INDENT if root . data > n1 and root . data > n2 : NEW_LINE INDENT root = root . left NEW_LINE DEDENT elif root . data < n1 and root . data < n2 : NEW_LINE INDENT root = root . right NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT return root NEW_LINE DEDENT root = Node ( 20 ) NEW_LINE root . left = Node ( 8 ) NEW_LINE root . right = Node ( 22 ) NEW_LINE root . left . left = Node ( 4 ) NEW_LINE root . left . right = Node ( 12 ) NEW_LINE root . left . right . left = Node ( 10 ) NEW_LINE root . left . right . right = Node ( 14 ) NEW_LINE n1 = 10 ; n2 = 14 NEW_LINE t = lca ( root , n1 , n2 ) NEW_LINE print " LCA ▁ of ▁ % d ▁ and ▁ % d ▁ is ▁ % d " % ( n1 , n2 , t . data ) NEW_LINE n1 = 14 ; n2 = 8 NEW_LINE t = lca ( root , n1 , n2 ) NEW_LINE print " LCA ▁ of ▁ % d ▁ and ▁ % d ▁ is ▁ % d " % ( n1 , n2 , t . data ) NEW_LINE n1 = 10 ; n2 = 22 NEW_LINE t = lca ( root , n1 , n2 ) NEW_LINE print " LCA ▁ of ▁ % d ▁ and ▁ % d ▁ is ▁ % d " % ( n1 , n2 , t . data ) NEW_LINE