Count the Number of Good Nodes — Problem & Solution
Count the Number of Good Nodes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count the Number of Good Nodes is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An undirected tree has n nodes labelled 0 to n - 1 and is rooted at node 0. Its n - 1 edges are given in edges, each [ai, bi].
A node is good if all the subtrees rooted at its children have the same size (number of nodes). A leaf has no children, so it is always good.
Return the number of good nodes in the tree.
Example 1
Input: edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output: 7
Explanation: Every node is good: node 0's two child subtrees both have 3 nodes, nodes 1 and 2 each have two leaf children, and the leaves are good.
Example 2
Input: edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]
Output: 6
Explanation: Nodes 1, 2 and 3 have children of different subtree sizes; the other six are good.
Example 3
Input: edges = [[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]]
Output: 12
Explanation: Only node 9 is not good: its children's subtrees have sizes 2 and 1.
Constraints
2 <= n <= 10^5edges.length == n - 1edges[i].length == 20 <= ai, bi < nthe input is a valid tree
Hints for Count the Number of Good Nodes
Hint 1
Whether a node is good depends only on the sizes of its children's subtrees, so compute every subtree size first.
Hint 2
Subtree sizes come from one bottom-up pass: process nodes children-before-parents and add each node's size to its parent's.
Hint 3
Then, for each node, compare the sizes of its children (all neighbours except the parent) with the first child's size.
How to solve Count the Number of Good Nodes
Compute every subtree size once, then check each node's children against each other. Each edge is looked at a constant number of times, so the whole thing is linear.
Approach
- Build adjacency lists and a BFS order from the root 0, recording each node's parent.
- Walk the BFS order backwards, adding
size[u]tosize[parent[u]](every size starts at 1). - For each node, scan its neighbours other than the parent; it is good if every such child has the same size as the first one (a leaf passes trivially).
- Return the count of good nodes.
Why it works
In reverse BFS order every child is finished before its parent, so size is exact when it is used. The goodness test is the definition applied directly.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The parent is a neighbour too — skip it, or the root's sizes get mixed with the whole tree's.
- A node with a single child is always good: one size is trivially equal to itself.
- Recursion over a long path can overflow the stack; the BFS order avoids it.
Reference solution
Python
from typing import List
def countGoodNodes(edges: List[List[int]]) -> int:
n = len(edges) + 1
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
parent = [-2] * n
parent[0] = -1
order = [0]
for u in order:
for v in adj[u]:
if parent[v] == -2:
parent[v] = u
order.append(v)
size = [1] * n
for u in reversed(order):
if parent[u] >= 0:
size[parent[u]] += size[u]
good = 0
for u in range(n):
first = -1
ok = True
for v in adj[u]:
if v == parent[u]:
continue
if first == -1:
first = size[v]
elif size[v] != first:
ok = False
break
if ok:
good += 1
return goodJava
public static int countGoodNodes(int[][] edges) {
int n = edges.length + 1;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
int[] parent = new int[n], order = new int[n], size = new int[n];
Arrays.fill(parent, -2);
Arrays.fill(size, 1);
parent[0] = -1;
int tail = 0;
order[tail++] = 0;
for (int h = 0; h < tail; h++) {
int u = order[h];
for (int v : adj.get(u)) if (parent[v] == -2) { parent[v] = u; order[tail++] = v; }
}
for (int t = n - 1; t > 0; t--) size[parent[order[t]]] += size[order[t]];
int good = 0;
for (int x = 0; x < n; x++) {
int first = -1;
boolean ok = true;
for (int c : adj.get(x)) {
if (c == parent[x]) continue;
if (first == -1) first = size[c];
else if (size[c] != first) { ok = false; break; }
}
if (ok) good++;
}
return good;
}C++
int countGoodNodes(vector<vector<int>>& edges) {
int n = edges.size() + 1;
vector<vector<int>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
vector<int> parent(n, -2), size(n, 1), order;
parent[0] = -1;
order.push_back(0);
for (size_t h = 0; h < order.size(); h++) {
int u = order[h];
for (int v : adj[u]) if (parent[v] == -2) { parent[v] = u; order.push_back(v); }
}
for (int t = n - 1; t > 0; t--) size[parent[order[t]]] += size[order[t]];
int good = 0;
for (int x = 0; x < n; x++) {
int first = -1;
bool ok = true;
for (int c : adj[x]) {
if (c == parent[x]) continue;
if (first == -1) first = size[c];
else if (size[c] != first) { ok = false; break; }
}
if (ok) good++;
}
return good;
}JavaScript
var countGoodNodes = function(edges) {
var n = edges.length + 1;
var adj = [], parent = [], size = [];
for (var i = 0; i < n; i++) { adj.push([]); parent.push(-2); size.push(1); }
for (var e = 0; e < edges.length; e++) {
adj[edges[e][0]].push(edges[e][1]);
adj[edges[e][1]].push(edges[e][0]);
}
parent[0] = -1;
var order = [0];
for (var h = 0; h < order.length; h++) {
var u = order[h];
for (var j = 0; j < adj[u].length; j++) {
var v = adj[u][j];
if (parent[v] === -2) { parent[v] = u; order.push(v); }
}
}
for (var t = n - 1; t > 0; t--) size[parent[order[t]]] += size[order[t]];
var good = 0;
for (var x = 0; x < n; x++) {
var first = -1, ok = true;
for (var k = 0; k < adj[x].length; k++) {
var c = adj[x][k];
if (c === parent[x]) continue;
if (first === -1) first = size[c];
else if (size[c] !== first) { ok = false; break; }
}
if (ok) good++;
}
return good;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals