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

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

✓ Brute Force - Traverse Each Subtree

⏱️ Time: O(n²) Space: O(n)

For every node, we build the tree and then perform a separate DFS traversal to count all nodes in its subtree that have the same label. This requires n separate DFS traversals.

Optimized DFS with Label Counting

⏱️ Time: O(n) Space: O(n)

Use a single DFS traversal starting from root. Each node collects label counts from its children's subtrees, adds its own contribution, and returns the counts to its parent. This way each node is visited exactly once.

Brute Force - Traverse Each Subtree — Algorithm Steps

Build adjacency list from edges
For each node i, start DFS from i
In DFS, count nodes with same label as i
Store count in result array

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Create adjacency list from edges

For Each Node

Start DFS to count matching labels in subtree

Count Matches

DFS visits all nodes in subtree, counting same labels

Code -

solution.c — C

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

typedef struct {
    char key;
    int value;
} MapEntry;

typedef struct {
    MapEntry* entries;
    int size;
    int capacity;
} Map;

Map* createMap() {
    Map* map = malloc(sizeof(Map));
    map->entries = malloc(26 * sizeof(MapEntry));
    map->size = 0;
    map->capacity = 26;
    return map;
}

int getFromMap(Map* map, char key) {
    for (int i = 0; i < map->size; i++) {
        if (map->entries[i].key == key) {
            return map->entries[i].value;
        }
    }
    return 0;
}

void setInMap(Map* map, char key, int value) {
    for (int i = 0; i < map->size; i++) {
        if (map->entries[i].key == key) {
            map->entries[i].value = value;
            return;
        }
    }
    map->entries[map->size].key = key;
    map->entries[map->size].value = value;
    map->size++;
}

void addToMap(Map* map, char key, int value) {
    setInMap(map, key, getFromMap(map, key) + value);
}

void freeMap(Map* map) {
    free(map->entries);
    free(map);
}

Map* dfs(int node, int parent, int** adj, int* adjSizes, char* labels, int* result) {
    // Count of each label in this subtree
    Map* subtreeCount = createMap();
    setInMap(subtreeCount, labels[node], 1);
    
    for (int i = 0; i < adjSizes[node]; i++) {
        int neighbor = adj[node][i];
        if (neighbor != parent) {
            Map* childCount = dfs(neighbor, node, adj, adjSizes, labels, result);
            // Add child subtree counts to current subtree
            for (int j = 0; j < childCount->size; j++) {
                char label = childCount->entries[j].key;
                int count = childCount->entries[j].value;
                addToMap(subtreeCount, label, count);
            }
            freeMap(childCount);
        }
    }
    
    // Set result for current node
    result[node] = getFromMap(subtreeCount, labels[node]);
    return subtreeCount;
}

void parseArray(const char* str, int arr[][2], int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        if (*p == '[') {
            p++;
            arr[*size][0] = (int)strtol(p, (char**)&p, 10);
            while (*p == ' ' || *p == ',') p++;
            arr[*size][1] = (int)strtol(p, (char**)&p, 10);
            while (*p && *p != ']') p++;
            if (*p == ']') p++;
            (*size)++;
        } else {
            p++;
        }
    }
}

int* solution(int n, int edges[][2], 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;
    }
    
    int* result = (int*)malloc(n * sizeof(int));
    
    Map* rootResult = dfs(0, -1, adj, adjSizes, labels, result);
    freeMap(rootResult);
    
    // 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);
    
    // Parse edges
    int edges[1000][2];
    int edgesSize;
    parseArray(edgesStr, edges, &edgesSize);
    
    int* result = solution(n, edges, edgesSize, labels);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we perform DFS that visits O(n) nodes in worst case

✓ Linear Growth

Space Complexity

O(n)

Adjacency list takes O(n) space, DFS recursion stack takes O(n) space

⚡ 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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Traverse Each Subtree — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler