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

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

You are given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Input & Output

Example 1 — Basic Tree

$ Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"

› Output: [2,1,1,1,1,1,1]

💡 Note: Node 0 (label 'a'): subtree has nodes 0,1,2,3,4,5,6 with labels 'abaedcd', count of 'a' = 2. Node 1 (label 'b'): subtree has nodes 1,4,5 with labels 'bed', count of 'b' = 1.

Example 2 — All Same Labels

$ Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"

› Output: [4,2,1,1]

💡 Note: All nodes have label 'b'. Node 0's subtree contains all 4 nodes. Node 1's subtree contains nodes 1,2 (2 nodes). Leaves 2,3 each contain only themselves.

Example 3 — Single Path

$ Input: n = 3, edges = [[0,1],[1,2]], labels = "abc"

› Output: [1,1,1]

💡 Note: Each node has a unique label, so each subtree contains only 1 node with its own label.

Constraints

1 ≤ n ≤ 10⁵
edges.length == n - 1
edges[i].length == 2
0 ≤ a_i, b_i < n
a_i ≠ b_i
labels.length == n
labels is consisting of only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with n=7 nodes and labels 'abaedcd'

Count Process

For each node, count same labels in its subtree

Output Array

Result array where result[i] = count for node i

Key Takeaway

🎯 Key Insight: Use DFS post-order traversal to collect label counts from children and avoid redundant subtree visits

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is to use a single DFS traversal where each node collects label counts from its children's subtrees, adds its own label, and passes the aggregated counts to its parent. The optimal approach uses post-order DFS to avoid redundant traversals. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS with Label Counting	O(n)	O(n)	Single DFS traversal that counts labels for all nodes by passing counts from children to parents
Brute Force - Traverse Each Subtree	O(n²)	O(n)	For each node, perform DFS to count all nodes with same label in its subtree

Optimized DFS with Label Counting — Algorithm Steps

Build adjacency list from edges
Start DFS from root node 0
For each node, collect label counts from children
Add current node's label to counts
Return counts to parent

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin from root, visit children first (post-order)

Collect Counts

Each node gets label counts from its children

Add Self

Node adds its own label count and stores result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* result;

void dfs(int node, int parent, int** adj, int* adjSizes, char* labels, int* counts) {
    // Initialize counts for this subtree
    int subtreeCounts[26] = {0};
    
    // Get counts from all children
    for (int i = 0; i < adjSizes[node]; i++) {
        int neighbor = adj[node][i];
        if (neighbor != parent) {
            int childCounts[26] = {0};
            dfs(neighbor, node, adj, adjSizes, labels, childCounts);
            for (int j = 0; j < 26; j++) {
                subtreeCounts[j] += childCounts[j];
            }
        }
    }
    
    // Add current node's label
    int labelIdx = labels[node] - 'a';
    subtreeCounts[labelIdx]++;
    
    // Store result for current node
    result[node] = subtreeCounts[labelIdx];
    
    // Copy counts back to parent
    for (int i = 0; i < 26; i++) {
        counts[i] = subtreeCounts[i];
    }
}

int* solution(int n, int** edges, int edgesSize, char* labels) {
    // Build adjacency list
    int** adj = (int**)malloc(n * sizeof(int*));
    int* adjSizes = (int*)calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        adj[i] = (int*)malloc(n * sizeof(int));
    }
    
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        adj[u][adjSizes[u]++] = v;
        adj[v][adjSizes[v]++] = u;
    }
    
    result = (int*)malloc(n * sizeof(int));
    int rootCounts[26] = {0};
    dfs(0, -1, adj, adjSizes, labels, rootCounts);
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(adj[i]);
    }
    free(adj);
    free(adjSizes);
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char edgesStr[10000];
    scanf("%s", edgesStr);
    
    char labels[1001];
    scanf("%s", labels);
    
    // Simple parsing for edges
    int edges[1000][2];
    int edgesSize = 0;
    
    // Parse edges manually
    char* ptr = edgesStr + 1; // Skip '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgesSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            edges[edgesSize][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            edgesSize++;
        } else {
            ptr++;
        }
    }
    
    int** edgesPtrs = (int**)malloc(edgesSize * sizeof(int*));
    for (int i = 0; i < edgesSize; i++) {
        edgesPtrs[i] = edges[i];
    }
    
    int* result = solution(n, edgesPtrs, edgesSize, labels);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(edgesPtrs);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single DFS visits each node exactly once

✓ Linear Growth

Space Complexity

O(n)

Adjacency list takes O(n) space, recursion stack depth is O(n) in worst case

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS with Label Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler