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

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

What is this problem about?

The Number of Nodes in the Sub-Tree With the Same Label problem gives you a rooted tree where each node has a character label. For each node, count how many nodes in its subtree (including itself) have the same label. Return an array of counts. This coding problem uses post-order DFS with character frequency propagation.

Why is this asked in interviews?

Samsung and Uber ask this to test post-order DFS where each node aggregates information from its children. The key technique is returning a character frequency map from each subtree DFS and combining children's counts at the parent. The BFS, hash table, counting, DFS, and tree interview pattern is the core.

Algorithmic pattern used

Post-order DFS with frequency maps. Each DFS call returns a character count array (or dict) for its subtree. For each node: start with a count of 1 for its own label, then add counts from all children's returned maps. Store the count for the current node's own label in the result. Return the combined count map to the parent.

Example explanation

Tree: node 0 labeled 'a' → children [1('b'), 2('a')]. Node 1 → child [3('b')].

• DFS(3): return {b:1}. Result[3]=1.
• DFS(1): combine own {b:1} + child {b:1} = {b:2}. Result[1]=2.
• DFS(2): return {a:1}. Result[2]=1.
• DFS(0): combine own {a:1} + child1 {b:2} + child2 {a:1} = {a:2,b:2}. Result[0]=2. Result = [2, 2, 1, 1].

Common mistakes candidates make

• Not including the current node's own label in the count.
• Returning a shared mutable dict instead of a copy to the parent.
• Using BFS (harder to aggregate subtree results bottom-up).
• Off-by-one: initializing the count for the node's label at 0 instead of 1.

Interview preparation tip

Post-order DFS "propagate information from subtree to parent" is a reusable pattern. For this problem, the aggregation is character frequency addition. The returned frequency map acts as the subtree's summary. Practice similar problems: subtree sum, subtree node count, maximum depth with constraints. The pattern is always: recurse to children, combine their results, compute the current node's contribution, return to parent.