Count ancestors with smaller value for each node of a Binary Tree | Function to add an edge between nodes u and v ; Function to perform the DFS Traversal and store parent of each node ; Store the immediate parent ; Traverse the children of the current node ; Recursively call for function dfs for the child node ; Function to count the number of ancestors with values smaller than that of the current node ; Perform the DFS Traversal ; Traverse all the nodes ; Store the number of ancestors smaller than node ; Loop until parent [ node ] != - 1 ; If the condition satisfies , increment cnt by 1 ; Print the required result for the current node ; Driver Code ; Tree Formation
def add_edge ( u , v ) : NEW_LINE INDENT global adj NEW_LINE adj [ u ] . append ( v ) NEW_LINE adj [ v ] . append ( u ) NEW_LINE DEDENT def dfs ( u , par = - 1 ) : NEW_LINE INDENT global adj , parent NEW_LINE parent [ u ] = par NEW_LINE for child in adj [ u ] : NEW_LINE INDENT if ( child != par ) : NEW_LINE INDENT dfs ( child , u ) NEW_LINE DEDENT DEDENT DEDENT def countSmallerAncestors ( n ) : NEW_LINE INDENT global parent , adj NEW_LINE dfs ( 1 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT node = i NEW_LINE cnt = 0 NEW_LINE while ( parent [ node ] != - 1 ) : NEW_LINE INDENT if ( parent [ node ] < i ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT node = parent [ node ] NEW_LINE DEDENT print ( cnt , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 6 NEW_LINE adj = [ [ ] for i in range ( 10 ** 5 ) ] NEW_LINE parent = [ 0 ] * ( 10 ** 5 ) NEW_LINE add_edge ( 1 , 5 ) NEW_LINE add_edge ( 1 , 4 ) NEW_LINE add_edge ( 4 , 6 ) NEW_LINE add_edge ( 5 , 3 ) NEW_LINE add_edge ( 5 , 2 ) NEW_LINE countSmallerAncestors ( N ) NEW_LINE DEDENT