Count the Number of Good Nodes solution and explanation
6 more videos on this problem
3249 Count the Number of Good Nodes || How to 🤔 in Interview || Build Graph + DFS || MathAyush Rao · 11:20 · 2K views
3249. Count the Number of Good Nodes (Leetcode Medium)Programming Live with Larry · 8:32 · 1K views
Count the Number of Good Nodes | Graph | DFS | LeetCode 3249CodeInBits · 19:00 · 317 views
Leetcode 3249 | Count the Number of Good Nodes | Weekly Contest 410Road To FAANG · 10:18 · 123 views
Leetcode 3249 | Count the Number of Good Nodes | Weekly 410 contest | Solution in C++Shekhar Gupta · 14:10 · 88 views
3249. Count the Number of Good Nodes || C++ || Leetcode SolutionCodeQuest · 15:33 · 48 views
Leetcode 3249 - Count the Number of Good NodesAdam Lipson · 6:49 · 22 views
The problem
There is an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. You are given a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
A node is good if all the subtrees rooted at its children have the same size.
Return the number of good nodes in the given tree.
A subtree of treeName is a tree consisting of a node in treeName and all of its descendants.
Example 1:
Input: edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output: 7
Explanation:
All of the nodes of the given tree 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:
There are 6 good nodes in the given tree. They are colored in the image above.
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:
All nodes except node 9 are good.
Constraints:
2 <= n <= 105edges.length == n - 1edges[i].length == 20 <= ai, bi < n- The input is generated such that
edgesrepresents a valid tree.
Approach overview
Problem Overview: You are given an undirected tree with n nodes. A node is considered good if all of its child subtrees have the same size. Leaf nodes are automatically good because they have no children. The task is to count how many nodes satisfy this property.
Approach 1: DFS and Size Calculation (O(n) time, O(n) space)
The most direct strategy uses a single Depth-First Search traversal. Start from the root (usually node 0) and recursively compute the size of each subtree. For every node, iterate through its children and record the subtree size returned by DFS. If all recorded sizes are equal, the node is considered good. The subtree size for the current node is then 1 + sum(childSizes), which propagates upward in the recursion.
This works because DFS naturally processes children before their parent, so each node already knows the size of its descendants. During the DFS step you simply compare the first child subtree size with the rest. If any size differs, mark the node as not good. Each edge and node is visited once, giving O(n) time complexity with O(n) recursion stack and adjacency list storage.
Approach 2: DFS with Precomputed Subtree Sizes (O(n) time, O(n) space)
This variation separates the logic into two passes over the tree. The first DFS computes and stores the subtree size of every node in an array. The second traversal checks each node by iterating through its neighbors and considering only children (excluding the parent). Since subtree sizes are already known, you simply compare them directly without recomputation.
This approach improves code clarity in some languages such as Java or C#, where separating computation and validation can make recursion easier to maintain. The first pass fills a subtreeSize[] array, while the second pass checks whether all child subtree sizes match. The complexity remains O(n) time because each edge is processed a constant number of times, and O(n) space for the adjacency list and stored subtree sizes.
Both approaches rely on representing the input as an adjacency list and traversing it with DFS. The key observation is that subtree sizes fully determine whether a node qualifies as good. Once you know the size of every child subtree, verifying the condition becomes a simple equality check.
Recommended for interviews: The single-pass DFS that calculates subtree sizes while checking equality is the approach most interviewers expect. It demonstrates strong understanding of DFS traversal and recursive tree DP patterns. The two-pass version is still O(n) and easier to reason about, but the single-pass solution shows better algorithmic efficiency and control over recursion.
Approach 1: DFS and Size Calculation
This approach uses Depth First Search (DFS) to traverse the tree and determine the size of each subtree. A node is considered 'good' if all its direct child subtrees are of the same size. We traverse the tree starting at the root, using a recursive helper function to count the size of each subtree and verify the 'good' condition by comparing the sizes of all child subtrees.
def count_good_nodes(n, edges):
from collections import defaultdict
def dfs(node, parent):
subtree_size = 1
unique_sizes = set()
for neighbor in adj[node]:
if neighbor != parent:
size = dfs(neighbor, node)
unique_sizes.add(size)
subtree_size += size
if len(unique_sizes) <= 1:
good_nodes[0] += 1
return subtree_size
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
good_nodes = [0]
dfs(0, -1)
return good_nodes[0]
# Example usage
edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
print(count_good_nodes(7, edges))#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
vector<vector<int>> adj;
int dfs(int node, int parent, int &goodNodes) {
int subtreeSize = 1;
unordered_set<int> uniqueSizes;
for (int neighbor : adj[node]) {
if (neighbor != parent) {
int size = dfs(neighbor, node, goodNodes);
uniqueSizes.insert(size);
subtreeSize += size;
}
}
if (uniqueSizes.size() <= 1) {
goodNodes++;
}
return subtreeSize;
}
int countGoodNodes(int n, vector<vector<int>> &edges) {
adj.resize(n);
for (auto &edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
int goodNodes = 0;
dfs(0, -1, goodNodes);
return goodNodes;
}
int main() {
vector<vector<int>> edges = {{0,1},{0,2},{1,3},{1,4},{2,5},{2,6}};
cout << countGoodNodes(7, edges) << endl;
return 0;
}This Python solution uses an adjacency list to represent the tree and invokes a DFS from the root node to compute subtree sizes recursively. For each node, we maintain a set of unique subtree sizes for its children. If the set contains one or zero elements, it implies all the subtrees have the same size, marking the node as good.
Time Complexity: O(n), where n is the number of nodes, since we traverse each node once.
Space Complexity: O(n), for the adjacency list and the recursion stack.
Approach 2: DFS with Precomputed Subtree Sizes
In this approach, we first precompute the size of each subtree using DFS before validating the 'good' condition. This helps in making the second DFS for condition checking efficient by using already computed subtree sizes.
import java.util.*;
public class CountGoodNodes {
static class Tree {
List<List<Integer>> adj;
int[] subtreeSizes;
int goodNodeCount = 0;
public Tree(int n) {
adj = new ArrayList<>();
subtreeSizes = new int[n];
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
}
private void computeSubtreeSizes(int node, int parent) {
int size = 1;
for (int neighbor : adj.get(node)) {
if (neighbor != parent) {
computeSubtreeSizes(neighbor, node);
size += subtreeSizes[neighbor];
}
}
subtreeSizes[node] = size;
}
private void countGoodNodes(int node, int parent) {
Set<Integer> uniqueSizes = new HashSet<>();
for (int neighbor : adj.get(node)) {
if (neighbor != parent) {
uniqueSizes.add(subtreeSizes[neighbor]);
}
}
if (uniqueSizes.size() <= 1) {
goodNodeCount++;
}
for (int neighbor : adj.get(node)) {
if (neighbor != parent) {
countGoodNodes(neighbor, node);
}
}
}
public int resolveGoodNodes() {
computeSubtreeSizes(0, -1);
countGoodNodes(0, -1);
return goodNodeCount;
}
}
public static int countGoodNodes(int n, int[][] edges) {
Tree tree = new Tree(n);
for (int[] edge : edges) {
tree.adj.get(edge[0]).add(edge[1]);
tree.adj.get(edge[1]).add(edge[0]);
}
return tree.resolveGoodNodes();
}
public static void main(String[] args) {
int[][] edges = {{0,1},{0,2},{1,3},{1,4},{2,5},{2,6}};
System.out.println(countGoodNodes(7, edges));
}
}using System;
using System.Collections.Generic;
public class CountGoodNodes {
static List<List<int>> adj;
static int[] subtreeSizes;
static int goodNodeCount = 0;
static void ComputeSubtreeSizes(int node, int parent) {
int size = 1;
foreach(var neighbor in adj[node]) {
if (neighbor != parent) {
ComputeSubtreeSizes(neighbor, node);
size += subtreeSizes[neighbor];
}
}
subtreeSizes[node] = size;
}
static void CountGoodNodes(int node, int parent) {
HashSet<int> uniqueSizes = new HashSet<int>();
foreach(var neighbor in adj[node]) {
if (neighbor != parent) {
uniqueSizes.Add(subtreeSizes[neighbor]);
}
}
if (uniqueSizes.Count <= 1) {
goodNodeCount++;
}
foreach(var neighbor in adj[node]) {
if (neighbor != parent) {
CountGoodNodes(neighbor, node);
}
}
}
public static int CountGoodNodesMethod(int n, int[][] edges) {
adj = new List<List<int>>(n);
for (int i = 0; i < n; i++) adj.Add(new List<int>());
foreach (var edge in edges) {
adj[edge[0]].Add(edge[1]);
adj[edge[1]].Add(edge[0]);
}
subtreeSizes = new int[n];
ComputeSubtreeSizes(0, -1);
CountGoodNodes(0, -1);
return goodNodeCount;
}
static void Main() {
int[][] edges = new int[][] {
new int[] { 0, 1 }, new int[] { 0, 2 }, new int[] { 1, 3 }, new int[] { 1, 4 },
new int[] { 2, 5 }, new int[] { 2, 6 }
};
Console.WriteLine(CountGoodNodesMethod(7, edges));
}
}This Java solution separates the process into two main DFS traversals. The first DFS calculates the size of each subtree for all nodes. The second DFS checks the 'good' condition using the precomputed sizes, adding to the count if the condition is met.
Time Complexity: O(n), as we traverse the tree nodes twice, once for computing sizes and another for condition checking.
Space Complexity: O(n), required for the adjacency list, size array, and recursion stack.
Approach 3: DFS
First, we construct the adjacency list g of the tree based on the given edges edges, where g[a] represents all the neighboring nodes of node a.
Next, we design a function dfs(a, fa) to calculate the number of nodes in the subtree rooted at node a and to accumulate the count of good nodes. Here, fa represents the parent node of node a.
The execution process of the function dfs(a, fa) is as follows:
- Initialize variables
pre = -1,cnt = 1,ok = 1, representing the number of nodes in a subtree of nodea, the total number of nodes in all subtrees of nodea, and whether nodeais a good node, respectively. - Traverse all neighboring nodes
bof nodea. Ifbis not equal tofa, recursively calldfs(b, a), with the return value beingcur, and addcurtocnt. Ifpre < 0, assigncurtopre; otherwise, ifpreis not equal tocur, it means the number of nodes in different subtrees of nodeais different, and setokto0. - Finally, add
okto the answer and returncnt.
In the main function, we call dfs(0, -1) and return the final answer.
The time complexity is O(n), and the space complexity is O(n). Here, n represents the number of nodes.
function countGoodNodes(edges: number[][]): number {
const n = edges.length + 1;
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
let ans = 0;
const dfs = (a: number, fa: number): number => {
let [pre, cnt, ok] = [-1, 1, 1];
for (const b of g[a]) {
if (b !== fa) {
const cur = dfs(b, a);
cnt += cur;
if (pre < 0) {
pre = cur;
} else if (pre !== cur) {
ok = 0;
}
}
}
ans += ok;
return cnt;
};
dfs(0, -1);
return ans;
}func countGoodNodes(edges [][]int) (ans int) {
n := len(edges) + 1
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)
}
var dfs func(int, int) int
dfs = func(a, fa int) int {
pre, cnt, ok := -1, 1, 1
for _, b := range g[a] {
if b != fa {
cur := dfs(b, a)
cnt += cur
if pre < 0 {
pre = cur
} else if pre != cur {
ok = 0
}
}
}
ans += ok
return cnt
}
dfs(0, -1)
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS and Size Calculation | Time Complexity: O(n), where n is the number of nodes, since we traverse each node once. Space Complexity: O(n), for the adjacency list and the recursion stack. |
| DFS with Precomputed Subtree Sizes | Time Complexity: O(n), as we traverse the tree nodes twice, once for computing sizes and another for condition checking. Space Complexity: O(n), required for the adjacency list, size array, and recursion stack. |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Subtree Size Calculation | O(n) | O(n) | Best general solution. Computes subtree sizes and validates good nodes in a single DFS traversal. |
| DFS with Precomputed Subtree Sizes | O(n) | O(n) | Useful when separating computation and validation logic for clarity, especially in strongly typed languages. |
Frequently asked questions
Is Count the Number of Good Nodes easy or hard?
Count the Number of Good Nodes is generally classified as a medium difficulty tree problem. The main challenge is recognizing that subtree sizes must be computed with DFS before verifying the equality condition across children.
Count the Number of Good Nodes Python/Java solution
The typical implementation builds an adjacency list, then performs a DFS function that returns subtree size. In Python this is often written using recursion and lists, while Java implementations use ArrayList adjacency structures and recursive helper methods. Both follow the same O(n) DFS logic.
How to solve Count the Number of Good Nodes in O(n)?
Build an adjacency list for the tree and run a DFS from the root. During DFS, compute the subtree size for each child and store it. Compare all child subtree sizes for the current node; if they are equal, increment the good node count. Since each node is processed once, the total runtime is O(n).
What is the best approach for Count the Number of Good Nodes?
The optimal approach uses Depth-First Search (DFS) to compute subtree sizes while traversing the tree. For each node, compare the sizes of all child subtrees. If they are equal, the node is counted as good. This solution runs in O(n) time and O(n) space using an adjacency list and recursion.
Is Count the Number of Good Nodes asked at Google/Amazon/Meta?
Tree traversal and subtree size problems appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the pattern of computing subtree sizes with DFS and validating node conditions is a common interview topic.
What data structure is used in Count the Number of Good Nodes?
The core data structure is a tree represented using an adjacency list. Depth-First Search (DFS) is used to traverse the tree and compute subtree sizes. Arrays or lists store subtree sizes during recursion.
What is the time complexity of Count the Number of Good Nodes?
The optimal DFS solution runs in O(n) time where n is the number of nodes in the tree. Each node and edge is visited once while computing subtree sizes. The space complexity is O(n) due to the adjacency list representation and recursion stack.