LeetCode #3249 — MEDIUM

Count the Number of Good Nodes

Move from brute-force thinking to an efficient approach using tree strategy.

The Problem

Problem Statement

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] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i 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 <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
The input is generated such that edges represents a valid tree.

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Tree

Example 1

[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]

Example 2

[[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]

Example 3

[[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]]

Core Insight

What unlocks the optimal approach

Use DFS.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3249: Count the Number of Good Nodes
class Solution {
    private int ans;
    private List<Integer>[] g;

    public int countGoodNodes(int[][] edges) {
        int n = edges.length + 1;
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        dfs(0, -1);
        return ans;
    }

    private int dfs(int a, int fa) {
        int pre = -1, cnt = 1, ok = 1;
        for (int b : g[a]) {
            if (b != fa) {
                int cur = dfs(b, a);
                cnt += cur;
                if (pre < 0) {
                    pre = cur;
                } else if (pre != cur) {
                    ok = 0;
                }
            }
        }
        ans += ok;
        return cnt;
    }
}

// Accepted solution for LeetCode #3249: Count the Number of Good Nodes
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
}

# Accepted solution for LeetCode #3249: Count the Number of Good Nodes
class Solution:
    def countGoodNodes(self, edges: List[List[int]]) -> int:
        def dfs(a: int, fa: int) -> int:
            pre = -1
            cnt = ok = 1
            for b in g[a]:
                if b != fa:
                    cur = dfs(b, a)
                    cnt += cur
                    if pre < 0:
                        pre = cur
                    elif pre != cur:
                        ok = 0
            nonlocal ans
            ans += ok
            return cnt

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        ans = 0
        dfs(0, -1)
        return ans

// Accepted solution for LeetCode #3249: Count the Number of Good Nodes
/**
 * [3249] Count the Number of Good Nodes
 */
pub struct Solution {}

// submission codes start here

impl Solution {
    pub fn count_good_nodes(edges: Vec<Vec<i32>>) -> i32 {
        let n = edges.len() + 1;
        let mut matrix = vec![vec![]; n];

        edges
            .into_iter()
            .map(|edge| (edge[0] as usize, edge[1] as usize))
            .for_each(|(x, y)| {
                matrix[x].push(y);
                matrix[y].push(x);
            });

        let mut result = 0;
        Self::dfs(&matrix, 0, usize::MAX, &mut result);
        result
    }

    fn dfs(tree: &Vec<Vec<usize>>, node: usize, parent: usize, result: &mut i32) -> i32 {
        if tree[node].len() == 0 {
            *result += 1;
            return 1;
        }

        let children: Vec<i32> = tree[node]
            .iter()
            .filter_map(|&child| {
                if child == parent {
                    None
                } else {
                    Some(Self::dfs(tree, child, node, result))
                }
            })
            .collect();

        if children.iter().all(|x| *x == children[0]) {
            *result += 1;
        }

        children.into_iter().sum::<i32>() + 1
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_3249() {
        assert_eq!(
            7,
            Solution::count_good_nodes(vec![
                vec![0, 1],
                vec![0, 2],
                vec![1, 3],
                vec![1, 4],
                vec![2, 5],
                vec![2, 6]
            ])
        );

        assert_eq!(
            6,
            Solution::count_good_nodes(vec![
                vec![0, 1],
                vec![1, 2],
                vec![2, 3],
                vec![3, 4],
                vec![0, 5],
                vec![1, 6],
                vec![2, 7],
                vec![3, 8]
            ])
        );

        assert_eq!(
            6,
            Solution::count_good_nodes(vec![
                vec![6, 0],
                vec![1, 0],
                vec![5, 1],
                vec![2, 5],
                vec![3, 1],
                vec![4, 3]
            ])
        );
    }
}

// Accepted solution for LeetCode #3249: Count the Number of Good 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;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(n)

Approach Breakdown

LEVEL ORDER

O(n) time

O(n) space

BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.

DFS TRAVERSAL

O(n) time

O(h) space

Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.

Shortcut: Visit every node once → O(n) time. Recursion depth = tree height → O(h) space.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Forgetting null/base-case handling

Wrong move: Recursive traversal assumes children always exist.

Usually fails on: Leaf nodes throw errors or create wrong depth/path values.

Fix: Handle null/base cases before recursive transitions.

Count the Number of Good Nodes

Problem Statement

Roadmap

Brute Force Baseline

Baseline thinking

Example 1

Example 2

Example 3

Related Problems

Core Insight

What unlocks the optimal approach

Algorithm Walkthrough

Iteration Checklist

Edge Cases

Full Annotated Code

Interactive Study Demo

Complexity Analysis

Approach Breakdown

Common Mistakes

Forgetting null/base-case handling