Count ancestors with smaller value for each node of a Binary Tree

#include <bits/stdc++.h>

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;

}

Let's block ads! (Why?)