Print common nodes on path from root ( or common ancestors ) | Utility class to create a new tree Node ; Utility function to find the LCA of two given values n1 and n2 . ; 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 - None , 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 ; Utility Function to print all ancestors of LCA ; base cases ; If target is present in either left or right subtree of this node , then prthis node ; Else return False ; Function to find nodes common to given two nodes ; Driver Code ; Let us create binary tree given in the above example
class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def findLCA ( root , n1 , n2 ) : NEW_LINE INDENT if ( root == 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 if ( left_lca != None ) : NEW_LINE INDENT return left_lca NEW_LINE DEDENT else : NEW_LINE INDENT return right_lca NEW_LINE DEDENT DEDENT def printAncestors ( root , target ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( root . key == target ) : NEW_LINE INDENT print ( root . key , end = " ▁ " ) NEW_LINE return True NEW_LINE DEDENT if ( printAncestors ( root . left , target ) or printAncestors ( root . right , target ) ) : NEW_LINE INDENT print ( root . key , end = " ▁ " ) NEW_LINE return True NEW_LINE DEDENT return False NEW_LINE DEDENT def findCommonNodes ( root , first , second ) : NEW_LINE INDENT LCA = findLCA ( root , first , second ) NEW_LINE if ( LCA == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT printAncestors ( root , LCA . key ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 3 ) NEW_LINE root . left . left = newNode ( 4 ) NEW_LINE root . left . right = newNode ( 5 ) NEW_LINE root . right . left = newNode ( 6 ) NEW_LINE root . right . right = newNode ( 7 ) NEW_LINE root . left . left . left = newNode ( 8 ) NEW_LINE root . right . left . left = newNode ( 9 ) NEW_LINE root . right . left . right = newNode ( 10 ) NEW_LINE if ( findCommonNodes ( root , 9 , 7 ) == False ) : NEW_LINE INDENT print ( " No ▁ Common ▁ nodes " ) NEW_LINE DEDENT DEDENT