#1519

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

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

Compute the number of nodes in each subtree sharing the same label using DFS with hash table aggregation efficiently.

hash table tree depth first search breadth first search counting

Problem Statement

You are given a tree with n nodes labeled from 0 to n-1. The tree is represented by n-1 edges in an undirected array, and each node has a lowercase English letter label given in a string labels. The tree is rooted at node 0.

Return an array ans of length n where ans[i] represents the number of nodes in the subtree rooted at node i that share the same label as node i. Each subtree includes its root node, and edges define the connectivity of the tree.

Examples

Example 1

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]

Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree. Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2

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

Output: [4,2,1,1]

The sub-tree of node 2 contains only node 2, so the answer is 1. The sub-tree of node 3 contains only node 3, so the answer is 1. The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2. The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"

Output: [3,2,1,1,1]

Example details omitted.

Constraints

1 <= n <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
labels.length == n
labels is consisting of only of lowercase English letters.

Solution Approach

Depth-First Search with Label Count Aggregation

Traverse the tree recursively using DFS. For each node, collect label counts from its children and merge them with its own label. Store the final count of the node's label in the answer array and return the aggregated frequency map to the parent node.

Use Hash Table for Frequency Tracking

At each node, maintain a hash table mapping labels to counts. When visiting children, combine their hash tables with the parent's table to keep track of how many nodes of each label exist in the subtree, allowing O(1) label count updates per node.

Avoid Double Counting and Cycles

Mark visited nodes or pass a parent reference to avoid revisiting nodes. Each node should contribute exactly once to its parent’s count to ensure correct label aggregation and prevent infinite loops in the traversal.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node and edge is visited once during DFS. Space complexity is O(n * 26) due to hash tables tracking lowercase letters in each subtree.

What Interviewers Usually Probe

DFS recursion with aggregation is expected rather than BFS.
Hash table usage for counting labels shows understanding of subtree state tracking.
Candidates should avoid global counters to prevent incorrect subtree counts.

Common Pitfalls or Variants

Common pitfalls

Failing to include the current node in its own subtree count.
Merging hash tables incorrectly, leading to undercounted labels.
Revisiting nodes without a parent check, causing infinite recursion or double counting.

Follow-up variants

Count nodes in subtrees that match any of a set of target labels.
Compute subtree label counts in a tree with weighted edges affecting traversal.
Return not only counts but also lists of nodes per label in each subtree.

FAQ

What is the best approach to solve Number of Nodes in the Sub-Tree With the Same Label?

Use DFS to traverse the tree and a hash table at each node to count labels, aggregating child counts to the parent node.

Can I solve this problem iteratively instead of using DFS recursion?

Yes, an iterative DFS using a stack can work, but you must carefully aggregate label counts while backtracking.

How do I handle large trees efficiently?

Limit the hash table size to 26 for lowercase letters and process each node exactly once to maintain O(n) time and space.

Do I need to consider the order of edges in the input?

No, as long as you correctly build the adjacency list and traverse from the root, edge order does not affect the label counts.

Why is hash table aggregation preferred in this subtree label counting problem?

It allows combining counts from children without iterating over all subtree nodes repeatedly, ensuring efficient O(n) computation.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
        def dfs(i, fa):
            ans[i] -= cnt[labels[i]]
            cnt[labels[i]] += 1
            for j in g[i]:
                if j != fa:
                    dfs(j, i)
            ans[i] += cnt[labels[i]]

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        cnt = Counter()
        ans = [0] * n
        dfs(0, -1)
        return ans

Continue Practicing

#1443 minimum time to collect all apples in a tree #1261 find elements in a contaminated binary tree #1123 lowest common ancestor of deepest leaves