3249. Count the Number of Good Nodes LeetCode Solution

In this guide, you will get 3249. Count the Number of Good Nodes LeetCode Solution with the best time and space complexity. The solution to Count the Number of Good Nodes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count the Number of Good Nodes solution in C++
Count the Number of Good Nodes solution in Java
Count the Number of Good Nodes solution in Python
Additional Resources

3249. Count the Number of Good Nodes LeetCode Solution image

Problem Statement of Count the Number of Good Nodes

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 <= 105
edges.length == n – 1
edges[i].length == 2
0 <= ai, bi < n
The input is generated such that edges represents a valid tree.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

3249. Count the Number of Good Nodes LeetCode Solution in C++

class Solution {
 public:
  int countGoodNodes(vector<vector<int>>& edges) {
    const int n = edges.size() + 1;
    int ans = 0;
    vector<vector<int>> graph(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    dfs(graph, 0, /*prev=*/-1, ans);
    return ans;
  }

 private:
  int ans = 0;

  // Returns the size of the subtree rooted at u.
  int dfs(const vector<vector<int>>& graph, int u, int prev, int& ans) {
    int size = 1;
    vector<int> childrenSizes;

    for (const int v : graph[u]) {
      if (v == prev)
        continue;
      const int childSize = dfs(graph, v, u, ans);
      size += childSize;
      childrenSizes.push_back(childSize);
    }

    if (childrenSizes.empty() || allSameSizes(childrenSizes))
      ++ans;

    return size;
  }

 private:
  bool allSameSizes(const vector<int>& childrenSizes) {
    for (int i = 1; i < childrenSizes.size(); ++i)
      if (childrenSizes[i] != childrenSizes[0])
        return false;
    return true;
  }
};
/* code provided by PROGIEZ */

3249. Count the Number of Good Nodes LeetCode Solution in Java

class Solution {
  public int countGoodNodes(int[][] edges) {
    final int n = edges.length + 1;
    List<Integer>[] graph = new ArrayList<>(n);

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      graph[u].add(v);
      graph[v].add(u);
    }

    dfs(graph, 0, -1);
    return ans;
  }

  private int ans = 0;

  // Returns the size of the subtree rooted at u.
  private int dfs(List<Integer>[] graph, int u, int prev) {
    int size = 1;
    List<Integer> childrenSizes = new ArrayList<>();

    for (final int v : graph[u]) {
      if (v == prev)
        continue;
      final int childSize = dfs(graph, v, u);
      size += childSize;
      childrenSizes.add(childSize);
    }

    if (childrenSizes.isEmpty() || allSameSizes(childrenSizes))
      ++ans;

    return size;
  }

  private boolean allSameSizes(List<Integer> childrenSizes) {
    for (int i = 1; i < childrenSizes.size(); ++i)
      if (!childrenSizes.get(i).equals(childrenSizes.get(0)))
        return false;
    return true;
  }
}
// code provided by PROGIEZ

3249. Count the Number of Good Nodes LeetCode Solution in Python

class Solution:
  def countGoodNodes(self, edges: list[list[int]]) -> int:
    n = len(edges) + 1
    graph = [[] for _ in range(n)]

    for u, v in edges:
      graph[u].append(v)
      graph[v].append(u)

    ans = 0

    def dfs(u: int, prev: int) -> int:
      """Returns the size of the subtree rooted at u."""
      nonlocal ans
      size = 1
      childrenSizes = []
      for v in graph[u]:
        if v == prev:
          continue
        child_size = dfs(v, u)
        size += child_size
        childrenSizes.append(child_size)

      if not childrenSizes or all(s == childrenSizes[0]
                                  for s in childrenSizes):
        ans += 1

      return size

    dfs(0, -1)
    return ans
 # code by PROGIEZ