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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void add_edge ( vector < int > adj [ ] , int u , int v ) { adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } void dfs ( vector < int > & parent , vector < int > adj [ ] , int u , int par = -1 ) { parent [ u ] = par ; for ( auto child : adj [ u ] ) { if ( child != par ) dfs ( parent , adj , child , u ) ; } } void countSmallerAncestors ( vector < int > adj [ ] , int n ) { vector < int > parent ( int ( 1e5 ) , 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 ] ; } cout << cnt << " ▁ " ; } } int main ( ) { int N = 6 ; vector < int > adj [ int ( 1e5 ) ] ; 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 ) ; return 0 ; }