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 ; 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
function add_edge ( adj , u , v ) { adj [ u ] . push ( v ) ; adj [ v ] . push ( u ) ; } function dfs ( parent , adj , u , par = - 1 ) { parent [ u ] = par ; adj [ u ] . forEach ( child => { if ( child != par ) dfs ( parent , adj , child , u ) ; } ) ; } function countSmallerAncestors ( adj , n ) { var parent = Array ( 100000 ) . fill ( 0 ) ; dfs ( parent , adj , 1 ) ; for ( var i = 1 ; i <= n ; i ++ ) { var node = i ; var cnt = 0 ; while ( parent [ node ] != - 1 ) { if ( parent [ node ] < i ) cnt += 1 ; node = parent [ node ] ; } document . write ( cnt + " " ) ; } } var N = 6 ; var adj = Array . from ( Array ( 100000 ) , ( ) => Array ( ) ) ; 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 ) ;