Check if two nodes are on same path in a tree | Set 2 | Function to filter the return Values ; Utility function to check if nodes are on same path or not ; Condition to check if any vertex is equal to given two vertex or not ; Check if the current position has 1 ; Recursive call ; Return LCA ; Function to check if nodes lies on same path or not ; Driver code
def filter ( x , y , z ) : NEW_LINE INDENT if ( x != - 1 and y != - 1 ) : NEW_LINE INDENT return z NEW_LINE DEDENT return y if x == - 1 else x NEW_LINE DEDENT def samePathUtil ( mtrx , vrtx , v1 , v2 , i ) : NEW_LINE INDENT ans = - 1 NEW_LINE if ( i == v1 or i == v2 ) : NEW_LINE INDENT return i NEW_LINE DEDENT for j in range ( 0 , vrtx ) : NEW_LINE INDENT if ( mtrx [ i ] [ j ] == 1 ) : NEW_LINE INDENT ans = filter ( ans , samePathUtil ( mtrx , vrtx , v1 , v2 , j ) , i ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def isVertexAtSamePath ( mtrx , vrtx , v1 , v2 , i ) : NEW_LINE INDENT lca = samePathUtil ( mtrx , vrtx , v1 - 1 , v2 - 1 , i ) NEW_LINE if ( lca == v1 - 1 or lca == v2 - 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT vrtx = 7 NEW_LINE edge = 6 NEW_LINE mtrx = [ [ 0 , 1 , 1 , 1 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 1 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 1 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 1 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 0 , 0 ] ] NEW_LINE v1 = 1 NEW_LINE v2 = 5 NEW_LINE if ( isVertexAtSamePath ( mtrx , vrtx , v1 , v2 , 0 ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT