hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Number of Nodes in the Sub-Tree With the Same Label


  • Approach:

    1. The things that are varied in each node are the counts of labels of subtree under a root.

    2. That simply means we need to find some way to propagate the counts of the label of the child to its root.

    3. Now, the subtree of a root might have different alphabets underneath its subtree.

    4. That simply means each node needs to return its count of labels to its root.

    5. Later the subtree counts will be accumulated for the root's count.

    6. Declare a graph, and a vector/list ans to store the answer.

    7. Start a DFS that will return a vector of frequency of each alphabet underneath a root.

    8. For each node, access each of its child nodes.

    9. Sum up the frequencies of alphabets for each child node.

    10. Increase the frequency count for the label of the root.

    11. And assign the increased count to ans[root].

    12. Return the frequency count list.


  • Time and Space Complexity:

      • Time Complexity: O(N*26)

      • Space Complexity: O(N)


Code [C++]

class Solution {

public:


vector<int>solve(int node, vector<vector<int>> &graph, vector<int> & ans, string & labels, int parent){

vector<int>countFreq(26, 0);

for(int i=0; i<graph[node].size(); i++){

int child = graph[node][i];

if(child == parent) continue;

vector<int>childFreq = solve(child, graph, ans, labels, node);

for(int j=0; j<26; j++){

countFreq[j] += childFreq[j];

}

}

countFreq[labels[node]-'a']++;

ans[node] = countFreq[labels[node]-'a'];

return countFreq;

}


vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {

vector<vector<int>>graph(n);

for(int i=0; i<edges.size(); i++){

int u = edges[i][0];

int v = edges[i][1];

graph[u].push_back(v);

graph[v].push_back(u);

}


vector<int>ans(n, 0);

solve(0, graph, ans, labels, 0);

return ans;

}

};