Easy backtracking approach

#include<bits/stdc++.h>

void helper(list<int>* adj, vector<int> &nodeBehaviour, int root, vector<bool> &vis, int G, int &res){
    if(nodeBehaviour[root-1]==1){
        G--;
    }
    if(G<0){
        return;
    }
    if(adj[root].size()==1){
        res++;
        return;
    }
    vis[root]=true;
    for(auto nei: adj[root]){
        if(vis[nei]==false){
            helper(adj,nodeBehaviour,nei,vis,G,res);
        }
    }
    vis[root]=false;
}

int Solution::solve(vector<int> &nodeBehaviour, vector<vector<int>> &edges, int goodNode){
    int V=nodeBehaviour.size();
    list<int> adj[V+1];
    for(auto vec: edges){
        adj[vec[0]].push_back(vec[1]);
        adj[vec[1]].push_back(vec[0]);
    }
    vector<bool> vis(V+1,false);
    int res=0;
    helper(adj,nodeBehaviour,1,vis,goodNode,res);
    return res;
}

Click here to start solving coding interview questions