How do you solve Count the Number of Good Nodes on LeetCode?

Count the Number of Good Nodes (LeetCode #3249) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Good nodes are defined by uniform subtree sizes.

What is the time complexity of Count the Number of Good Nodes?

The optimal solution for Count the Number of Good Nodes runs in O(n) time and uses O(n) space. This complexity is efficient because we only traverse the tree once, collecting sizes and checking conditions in a single pass.

What is the brute force solution for Count the Number of Good Nodes?

The brute force approach for Count the Number of Good Nodes is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we can check each node and its children to see if all subtrees have the same size. This involves traversing the tree multiple times, leading to inefficiency. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Count the Number of Good Nodes?

Count the Number of Good Nodes uses the following concepts: Tree, Depth-First Search. The recommended patterns to study are: Depth-First Search, Tree Traversal.

What are the interview tips for Count the Number of Good Nodes?

Clarify the definition of 'good nodes' before starting. Think about tree traversal methods (DFS/BFS) and their implications. Practice visualizing tree structures to better understand relationships.

What are common mistakes when solving Count the Number of Good Nodes?

Not considering the parent node during traversal, leading to incorrect size calculations. Failing to check if all child subtree sizes are the same.

#3249

Count the Number of Good Nodes

Medium

TreeDepth-First SearchDepth-First SearchTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

In the optimal approach, we use a single DFS traversal to calculate subtree sizes and check if all children of a node have the same size, thus reducing the number of traversals.

⚙️

Algorithm

5 steps

1Step 1: Build the tree using an adjacency list from the edges.
2Step 2: Perform a DFS starting from the root node (0).
3Step 3: For each node, collect the sizes of its children's subtrees.
4Step 4: Check if all sizes are the same; if so, increment the good node count.
5Step 5: Return the total count of good nodes.

solution.py24 lines

1# Full working Python code
2class Solution:
3    def countGoodNodes(self, edges):
4        from collections import defaultdict
5        tree = defaultdict(list)
6        for a, b in edges:
7            tree[a].append(b)
8            tree[b].append(a)
9
10        good_count = 0
11
12        def dfs(node, parent):
13            nonlocal good_count
14            sizes = []
15            for child in tree[node]:
16                if child != parent:
17                    sizes.append(dfs(child, node))
18            if len(set(sizes)) <= 1:
19                good_count += 1
20            return len(sizes) + 1
21
22        dfs(0, -1)
23        return good_count
24

ℹ

Complexity note: This complexity is efficient because we only traverse the tree once, collecting sizes and checking conditions in a single pass.

1Good nodes are defined by uniform subtree sizes.
2DFS is effective for tree traversal and size calculation.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.