Count ancestors with smaller value for each node of a Binary Tree | C # program for the above approach ; 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 ; Stores the parent of each 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
using System ; using System . Collections . Generic ; class GFG { static void add_edge ( List < List < int > > adj , int u , int v ) { adj [ u ] . Add ( v ) ; adj [ v ] . Add ( u ) ; } static void dfs ( List < int > parent , List < List < int > > adj , int u , int par = - 1 ) { parent [ u ] = par ; foreach ( int child in adj [ u ] ) { if ( child != par ) dfs ( parent , adj , child , u ) ; } } static void countSmallerAncestors ( List < List < int > > adj , int n ) { List < int > parent = new List < int > ( ) ; for ( int i = 0 ; i < ( int ) ( 1e5 ) ; i ++ ) { parent . Add ( 0 ) ; } dfs ( parent , adj , 1 ) ; for ( int i = 1 ; i <= n ; i ++ ) { int node = i ; int cnt = 0 ; while ( parent [ node ] != - 1 ) { if ( parent [ node ] < i ) cnt += 1 ; node = parent [ node ] ; } Console . Write ( cnt + " ▁ " ) ; } } static void Main ( ) { int N = 6 ; List < List < int > > adj = new List < List < int > > ( ) ; for ( int i = 0 ; i < ( int ) ( 1e5 ) ; i ++ ) { adj . Add ( new List < int > ( ) ) ; } add_edge ( adj , 1 , 5 ) ; add_edge ( adj , 1 , 4 ) ; add_edge ( adj , 4 , 6 ) ; add_edge ( adj , 5 , 3 ) ; add_edge ( adj , 5 , 2 ) ; countSmallerAncestors ( adj , N ) ; } }