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

Problem Overview: You are given an undirected tree with n nodes where each node has a lowercase character label. For every node, compute how many nodes inside its subtree (including itself) share the same label. The output is an array where ans[i] represents this count for node i.

The structure is a tree, which means there is exactly one path between any two nodes. This naturally leads to traversal strategies such as Depth-First Search or Breadth-First Search. The key observation: while returning from a DFS call, you already know the label distribution of the entire subtree.

Approach 1: DFS with Frequency Array (O(n) time, O(n) space)

Build an adjacency list for the tree, then run DFS from the root (node 0). Each recursive call returns a frequency array of size 26 representing counts of labels inside that subtree. After visiting children, merge their frequency arrays into the current node's array. Increment the index corresponding to the current node’s label and record the result for that node.

The key insight: label counts naturally accumulate during the DFS backtracking phase. Since labels are lowercase English letters, using a fixed array of size 26 avoids expensive lookups. Each edge is processed once and each node merges child counts only once, giving O(n) time and O(n) space for recursion and adjacency storage. This approach avoids overhead from dynamic structures and performs well in practice.

Approach 2: DFS with HashMap (O(n) time, O(n) space)

Instead of a fixed array, maintain a HashMap<char, int> (or dictionary) for each subtree. During DFS, recursively collect maps from children, merge them into the current node’s map, then increment the count for the current node’s label. The answer for that node is simply the value associated with its label after merging.

This version relies on a Hash Table to store label frequencies. The algorithmic idea is identical to the array version: accumulate label counts bottom-up. The difference is flexibility—maps work even if the label space is large or unknown. The tradeoff is higher constant overhead due to hashing and map merges.

Recommended for interviews: DFS with a frequency array is the expected solution. It demonstrates understanding of tree traversal and efficient counting. Starting with a DFS explanation shows you recognize the subtree structure. Switching to a fixed 26-length array instead of a map shows attention to constant-factor optimization, which interviewers usually appreciate.