Count ancestors with smaller value for each node of a Binary Tree | Java 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
import java . io . * ; import java . util . * ; class GFG { static void add_edge ( ArrayList < ArrayList < Integer > > adj , int u , int v ) { adj . get ( u ) . add ( v ) ; adj . get ( v ) . add ( u ) ; } static void dfs ( ArrayList < Integer > parent , ArrayList < ArrayList < Integer > > adj , int u , int par ) { parent . set ( u , par ) ; for ( int child : adj . get ( u ) ) { if ( child != par ) dfs ( parent , adj , child , u ) ; } } static void countSmallerAncestors ( ArrayList < ArrayList < Integer > > adj , int n ) { ArrayList < Integer > parent = new ArrayList < Integer > ( ) ; for ( int i = 0 ; i < ( int ) ( 1e5 ) ; i ++ ) { parent . add ( 0 ) ; } dfs ( parent , adj , 1 , - 1 ) ; for ( int i = 1 ; i <= n ; i ++ ) { int node = i ; int cnt = 0 ; while ( parent . get ( node ) != - 1 ) { if ( parent . get ( node ) < i ) cnt += 1 ; node = parent . get ( node ) ; } System . out . print ( cnt + " ▁ " ) ; } } public static void main ( String [ ] args ) { int N = 6 ; ArrayList < ArrayList < Integer > > adj = new ArrayList < ArrayList < Integer > > ( ) ; for ( int i = 0 ; i < ( int ) ( 1e5 ) ; i ++ ) { adj . add ( new ArrayList < Integer > ( ) ) ; } 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 ) ; } }