We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Medium

Problem Description

You are given a tree consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a label which is a lower-case character given in the string labels. The edges array represents connections between nodes. Return an array where ans[i] is the number of nodes in the subtree of the i-th node which have the same label as node i.

Key Insights

  • The tree is a connected, undirected graph with no cycles.
  • Each node is part of its own subtree.
  • Depth-First Search (DFS) can be employed to traverse the tree and count labels.
  • We can use a dictionary to keep track of label counts in each subtree.

Space and Time Complexity

Time Complexity: O(n) - Each node and edge is visited once. Space Complexity: O(n) - Space for the adjacency list representation and for storing counts.

Solution

The problem can be solved using a Depth-First Search (DFS) approach. We will represent the tree using an adjacency list. Starting from the root node (node 0), we will traverse the tree recursively. For each node, we will count the occurrences of its label in its subtree. We will use a dictionary to keep track of the counts of each label. The key steps are:

  1. Build the tree using the edges to create an adjacency list.
  2. Use DFS to traverse the tree, counting the occurrences of labels in each subtree.
  3. Store the results in an array to return the final counts for each node.

Code Solutions

def countSubtrees(n, edges, labels):
    from collections import defaultdict
    
    # Build the tree as an adjacency list
    tree = defaultdict(list)
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)

    # Result array
    result = [0] * n

    def dfs(node, parent):
        # Count of labels in the current subtree
        count = [0] * 26  # For 'a' to 'z'
        label_index = ord(labels[node]) - ord('a')
        count[label_index] += 1  # Count the current node's label

        for neighbor in tree[node]:
            if neighbor != parent:  # Avoid going back to parent
                child_count = dfs(neighbor, node)
                for i in range(26):
                    count[i] += child_count[i]  # Merge counts

        result[node] = count[label_index]  # Store count for the current node
        return count

    dfs(0, -1)  # Start DFS from the root node
    return result
← Back to All Questions