Number of Nodes in the Sub-Tree With the Same Label solution and explanation
9 more videos on this problem
Number of Nodes in the Sub-Tree With the Same Label : Explanation ➕ Live CodingcodestorywithMIK · 30:23 · 3K views
1519. Number of Nodes in the Sub-Tree With the Same Label (Leetcode Medium)Programming Live with Larry · 5:50 · 2K views
Daily Leetcode #1017: Jan 12, 2023 - 1519. Number of Nodes in the Sub-Tree With the Same LabelProgramming Live with Larry · 9:54 · 1K views
Number of Nodes in the Sub-Tree With the Same Label - DFS - PythonCheatCode Ninja · 6:44 · 802 views
1519. Number of Nodes in the Sub-Tree With the Same Label | LeetCode | C++Deep Tech · 11:33 · 411 views
1519. Number of Nodes in the Sub-Tree With the Same Label | JavaScript | DFS | LeetCode DailyLeetCodeWithMonu · 17:00 · 346 views
Leetcode 1519 Number of Nodes in the Sub-Tree With the Same Label (Java)TheAnalyticGuy · 9:10 · 320 views
Leetcode 1519: Number of Nodes in the Sub-Tree With the Same LabelAlgorithms Casts · 13:14 · 218 views
Number of Nodes in the Sub-Tree with the Same Label || Q. 1519 || Medium || Leetcode Daily ChallengeCodeRapt · 13:18 · 183 views
Number of Nodes in the Sub-Tree With the Same Label | LeetCode 1519 | JavaThe TryIt Project · 16:31 · 134 views
The 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.
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] Explanation: 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] Explanation: 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]
Constraints:
1 <= n <= 105edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != bilabels.length == nlabelsis consisting of only of lowercase English letters.
Approach overview
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.
Approach 1: DFS with Frequency Array
This approach utilizes a Depth First Search (DFS) to traverse each node of the tree. During traversal, we maintain a frequency array for each node to keep count of each label in its subtree. The recursion allows merging results from child nodes to calculate the current node's results.
from collections import defaultdict
class Solution:
def countSubTrees(self, n, edges, labels):
tree = defaultdict(list)
for a, b in edges:
tree[a].append(b)
tree[b].append(a)
result = [0] * n
count = [[0] * 26 for _ in range(n)]
def dfs(node, parent):
label_index = ord(labels[node]) - ord('a')
count[node][label_index] = 1
for child in tree[node]:
if child != parent:
dfs(child, node)
for i in range(26):
count[node][i] += count[child][i]
result[node] = count[node][label_index]
dfs(0, -1)
return resultimport java.util.ArrayList;
import java.util.List;
class Solution {
public int[] countSubTrees(int n, int[][] edges, String labels) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
int[] result = new int[n];
int[][] count = new int[n][26];
dfs(0, -1, graph, labels, count, result);
return result;
}
private void dfs(int node, int parent, List<List<Integer>> graph, String labels, int[][] count, int[] result) {
int labelIndex = labels.charAt(node) - 'a';
count[node][labelIndex] = 1;
for (int child : graph.get(node)) {
if (child == parent) continue;
dfs(child, node, graph, labels, count, result);
for (int i = 0; i < 26; i++) {
count[node][i] += count[child][i];
}
}
result[node] = count[node][labelIndex];
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
vector<vector<int>> graph(n);
for (const auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
vector<int> result(n, 0);
vector<vector<int>> count(n, vector<int>(26, 0));
dfs(0, -1, graph, labels, count, result);
return result;
}
private:
void dfs(int node, int parent, vector<vector<int>>& graph, string& labels, vector<vector<int>>& count, vector<int>& result) {
int labelIndex = labels[node] - 'a';
count[node][labelIndex] = 1;
for (int child : graph[node]) {
if (child == parent) continue;
dfs(child, node, graph, labels, count, result);
for (int i = 0; i < 26; ++i) {
count[node][i] += count[child][i];
}
}
result[node] = count[node][labelIndex];
}
};var countSubTrees = function(n, edges, labels) {
const graph = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
graph[a].push(b);
graph[b].push(a);
}
const result = Array(n).fill(0);
const count = Array.from({ length: n }, () => Array(26).fill(0));
const dfs = (node, parent) => {
const labelIndex = labels.charCodeAt(node) - 'a'.charCodeAt(0);
count[node][labelIndex] = 1;
for (const child of graph[node]) {
if (child === parent) continue;
dfs(child, node);
for (let i = 0; i < 26; i++) {
count[node][i] += count[child][i];
}
}
result[node] = count[node][labelIndex];
};
dfs(0, -1);
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void dfs(int node, int parent, int** graph, int* graphSize, char* labels, int* result, int** countArr) {
int labelIndex = labels[node] - 'a';
countArr[node][labelIndex] = 1;
for (int i = 0; i < graphSize[node]; i++) {
int child = graph[node][i];
if (child == parent) continue;
dfs(child, node, graph, graphSize, labels, result, countArr);
for (int j = 0; j < 26; j++) {
countArr[node][j] += countArr[child][j];
}
}
result[node] = countArr[node][labelIndex];
}
int* countSubTrees(int n, int** edges, int edgesSize, int* edgesColSize, char* labels, int* returnSize) {
int** graph = (int**)malloc(n * sizeof(int*));
int* graphSize = (int*)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
graph[i] = (int*)malloc(n * sizeof(int));
}
for (int i = 0; i < edgesSize; i++) {
int a = edges[i][0];
int b = edges[i][1];
graph[a][graphSize[a]++] = b;
graph[b][graphSize[b]++] = a;
}
int** countArr = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
countArr[i] = (int*)calloc(26, sizeof(int));
}
int* result = (int*)calloc(n, sizeof(int));
dfs(0, -1, graph, graphSize, labels, result, countArr);
*returnSize = n;
for (int i = 0; i < n; i++) {
free(graph[i]);
free(countArr[i]);
}
free(graph);
free(countArr);
free(graphSize);
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] CountSubTrees(int n, int[][] edges, string labels) {
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
int[] result = new int[n];
int[][] count = new int[n][];
for (int i = 0; i < n; i++) {
count[i] = new int[26];
}
Dfs(0, -1, graph, labels, count, result);
return result;
}
private void Dfs(int node, int parent, List<int>[] graph, string labels, int[][] count, int[] result) {
int labelIndex = labels[node] - 'a';
count[node][labelIndex] = 1;
foreach (var child in graph[node]) {
if (child == parent) continue;
Dfs(child, node, graph, labels, count, result);
for (int i = 0; i < 26; i++) {
count[node][i] += count[child][i];
}
}
result[node] = count[node][labelIndex];
}
}The Python solution constructs a tree using a defaultdict. The DFS traversal is used to keep a frequency array storing label counts for each node's subtree. As the function moves from child to parent nodes, it updates the current node's counts using its children's data. This is used to determine the result for each node.
The time complexity is O(n) because each node and edge is computed once in the DFS traversal. The space complexity is O(n) for the adjacency list and label frequencies.
Approach 2: DFS with HashMap
This alternative approach utilizes a HashMap to dynamically manage counts of node labels as opposed to fixed-size arrays. The hash map structure allows potential extension to accommodate varying character sets, though for this problem, it's implemented for the fixed set of labels 'a' to 'z'.
from collections import defaultdict
class Solution:
def countSubTrees(self, n, edges, labels):
tree = defaultdict(list)
for a, b in edges:
tree[a].append(b)
tree[b].append(a)
result = [0] * n
count = [defaultdict(int) for _ in range(n)]
def dfs(node, parent):
label = labels[node]
count[node][label] = 1
for child in tree[node]:
if child != parent:
dfs(child, node)
for key in count[child]:
count[node][key] += count[child][key]
result[node] = count[node][label]
dfs(0, -1)
return resultimport java.util.*;
class Solution {
public int[] countSubTrees(int n, int[][] edges, String labels) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
int[] result = new int[n];
List<Map<Character, Integer>> count = new ArrayList<>();
for (int i = 0; i < n; i++) {
count.add(new HashMap<>());
}
dfs(0, -1, graph, labels, count, result);
return result;
}
private void dfs(int node, int parent, List<List<Integer>> graph, String labels, List<Map<Character, Integer>> count, int[] result) {
char label = labels.charAt(node);
count.get(node).put(label, count.get(node).getOrDefault(label, 0) + 1);
for (int child : graph.get(node)) {
if (child == parent) continue;
dfs(child, node, graph, labels, count, result);
for (Map.Entry<Character, Integer> entry : count.get(child).entrySet()) {
count.get(node).put(entry.getKey(), count.get(node).getOrDefault(entry.getKey(), 0) + entry.getValue());
}
}
result[node] = count.get(node).get(label);
}
}#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
class Solution {
public:
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
vector<vector<int>> graph(n);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
vector<int> result(n, 0);
vector<unordered_map<char, int>> count(n);
dfs(0, -1, graph, labels, count, result);
return result;
}
private:
void dfs(int node, int parent, vector<vector<int>>& graph, string& labels, vector<unordered_map<char, int>>& count, vector<int>& result) {
char label = labels[node];
count[node][label] = 1;
for (int child : graph[node]) {
if (child == parent) continue;
dfs(child, node, graph, labels, count, result);
for (auto& [key, value] : count[child]) {
count[node][key] += value;
}
}
result[node] = count[node][label];
}
};var countSubTrees = function(n, edges, labels) {
const graph = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
graph[a].push(b);
graph[b].push(a);
}
const result = Array(n).fill(0);
const count = Array.from({ length: n }, () => new Map());
const dfs = (node, parent) => {
const label = labels[node];
count[node].set(label, (count[node].get(label) || 0) + 1);
for (const child of graph[node]) {
if (child === parent) continue;
dfs(child, node);
for (const [key, value] of count[child].entries()) {
count[node].set(key, (count[node].get(key) || 0) + value);
}
}
result[node] = count[node].get(label);
};
dfs(0, -1);
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int *counts;
int size;
} CountMap;
CountMap* createCountMap() {
CountMap* countMap = (CountMap*)malloc(sizeof(CountMap));
countMap->counts = (int*)calloc(26, sizeof(int));
countMap->size = 26;
return countMap;
}
void freeCountMap(CountMap* countMap) {
free(countMap->counts);
free(countMap);
}
void mergeMaps(CountMap* target, CountMap* source) {
for (int i = 0; i < source->size; i++) {
target->counts[i] += source->counts[i];
}
}
void dfs(int node, int parent, int** graph, int* graphSize, char* labels, int* result, CountMap** countMaps) {
int labelIndex = labels[node] - 'a';
countMaps[node]->counts[labelIndex] = 1;
for (int i = 0; i < graphSize[node]; i++) {
int child = graph[node][i];
if (child == parent) continue;
dfs(child, node, graph, graphSize, labels, result, countMaps);
mergeMaps(countMaps[node], countMaps[child]);
}
result[node] = countMaps[node]->counts[labelIndex];
}
int* countSubTrees(int n, int** edges, int edgesSize, int* edgesColSize, char* labels, int* returnSize) {
int** graph = (int**)malloc(n * sizeof(int*));
int* graphSize = (int*)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
graph[i] = (int*)malloc(n * sizeof(int));
}
for (int i = 0; i < edgesSize; i++) {
int a = edges[i][0];
int b = edges[i][1];
graph[a][graphSize[a]++] = b;
graph[b][graphSize[b]++] = a;
}
CountMap** countMaps = (CountMap**)malloc(n * sizeof(CountMap*));
for (int i = 0; i < n; i++) {
countMaps[i] = createCountMap();
}
int* result = (int*)calloc(n, sizeof(int));
dfs(0, -1, graph, graphSize, labels, result, countMaps);
*returnSize = n;
for (int i = 0; i < n; i++) {
free(graph[i]);
freeCountMap(countMaps[i]);
}
free(graph);
free(countMaps);
free(graphSize);
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] CountSubTrees(int n, int[][] edges, string labels) {
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
int[] result = new int[n];
List<Dictionary<char, int>> count = new List<Dictionary<char, int>>();
for (int i = 0; i < n; i++) {
count.Add(new Dictionary<char, int>());
}
Dfs(0, -1, graph, labels, count, result);
return result;
}
private void Dfs(int node, int parent, List<int>[] graph, string labels, List<Dictionary<char, int>> count, int[] result) {
char label = labels[node];
if (!count[node].ContainsKey(label)) count[node][label] = 0;
count[node][label]++;
foreach (var child in graph[node]) {
if (child == parent) continue;
Dfs(child, node, graph, labels, count, result);
foreach (var keyValue in count[child]) {
if (!count[node].ContainsKey(keyValue.Key)) count[node][keyValue.Key] = 0;
count[node][keyValue.Key] += keyValue.Value;
}
}
result[node] = count[node][label];
}
}The Python solution employs default dictionaries for flexible count management. This method handles character frequencies effectively during DFS and extends label counts through merging children’s data into parent nodes, leading to accurate output.
This approach has O(n) time complexity, tied to the linear nature of DFS, and O(n) space complexity, based on map-backed count structures.
Approach 3: Default Approach
function countSubTrees(n: number, edges: number[][], labels: string): number[] {
const dfs = (i: number, fa: number) => {
const k = labels.charCodeAt(i) - 97;
ans[i] -= cnt[k];
cnt[k]++;
for (const j of g[i]) {
if (j !== fa) {
dfs(j, i);
}
}
ans[i] += cnt[k];
};
const ans = new Array(n).fill(0),
cnt = new Array(26).fill(0);
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
dfs(0, -1);
return ans;
}func countSubTrees(n int, edges [][]int, labels string) []int {
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
ans := make([]int, n)
cnt := [26]int{}
var dfs func(int, int)
dfs = func(i, fa int) {
k := labels[i] - 'a'
ans[i] -= cnt[k]
cnt[k]++
for _, j := range g[i] {
if j != fa {
dfs(j, i)
}
}
ans[i] += cnt[k]
}
dfs(0, -1)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS with Frequency Array | The time complexity is O(n) because each node and edge is computed once in the DFS traversal. The space complexity is O(n) for the adjacency list and label frequencies. |
| DFS with HashMap | This approach has O(n) time complexity, tied to the linear nature of DFS, and O(n) space complexity, based on map-backed count structures. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Frequency Array | O(n) | O(n) | Best choice when labels are limited (like lowercase letters). Fastest and most common interview solution. |
| DFS with HashMap | O(n) | O(n) | Useful when label space is large or not fixed. Easier to reason about but slightly slower due to hashing. |
| BFS with Post-processing | O(n) | O(n) | Less common. Requires additional structures to aggregate subtree counts after traversal. |
Frequently asked questions
Is Number of Nodes in the Sub-Tree With the Same Label easy or hard?
The problem is classified as Medium on LeetCode. The main challenge is recognizing that subtree label counts should be aggregated during DFS backtracking. Once that insight is clear, the implementation becomes straightforward.
Number of Nodes in the Sub-Tree With the Same Label Python/Java solution
Both Python and Java implementations follow the same pattern: build an adjacency list, run DFS, maintain a frequency structure for labels, and update the result array during backtracking. Python typically uses lists for the 26-length frequency array, while Java uses int[26].
How to solve Number of Nodes in the Sub-Tree With the Same Label in O(n)?
Build an adjacency list for the tree and perform a DFS starting from node 0. Each DFS call returns a frequency count of labels in that subtree. Merge child frequencies into the parent, increment the count for the current node’s label, and record the value for the result array.
What is the best approach for Number of Nodes in the Sub-Tree With the Same Label?
DFS with a frequency array is the most efficient and commonly expected solution. During DFS, each node aggregates label counts from its children and updates its own label count. Because labels are limited to 26 lowercase letters, a fixed array avoids hashing overhead and keeps the algorithm O(n) time.
Is Number of Nodes in the Sub-Tree With the Same Label asked at Google/Amazon/Meta?
Tree traversal and DFS counting problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of subtree aggregation and label frequency counting are common patterns used to test recursion, graph traversal, and data structure knowledge.
What data structure is used in Number of Nodes in the Sub-Tree With the Same Label?
The solution primarily uses an adjacency list to represent the tree and DFS recursion for traversal. For counting labels, either a fixed frequency array of size 26 or a hash map can be used to track occurrences of characters within each subtree.
What is the time complexity of Number of Nodes in the Sub-Tree With the Same Label?
The optimal solution runs in O(n) time where n is the number of nodes in the tree. Each node is visited once during DFS and each edge is processed exactly once. Merging frequency arrays takes constant time because the array size is fixed (26).