> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/graph/dfs-bfs/3249.-count-the-number-of-good-nodes.md).

# 3249. Count the Number of Good Nodes

## Problem Statement

<br>

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&#x20;

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.

&#x20;

**Example 1:**

**Input:** edges = \[\[0,1],\[0,2],\[1,3],\[1,4],\[2,5],\[2,6]]

**Output:** 7

**Explanation:**

![](https://assets.leetcode.com/uploads/2024/05/26/tree1.png)

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:**

![](https://assets.leetcode.com/uploads/2024/06/03/screenshot-2024-06-03-193552.png)

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:**

![](https://assets.leetcode.com/uploads/2024/08/08/rob.jpg)

All nodes except node 9 are good.

&#x20;

**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.

## Intuition

```
Here,

1) Size is asked so number of nodes in Subtree
2) UNDIRECTED Tree mentioned so 

This means [x->y] and [y->x] can both be given in any order so Push_back in both


Other is standard DFS

```

### Links

<https://leetcode.com/problems/count-the-number-of-good-nodes/>

### Video Links

<https://www.youtube.com/watch?v=DimYkgJUiL0>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
/*
Two words:
Undirected Tree 
Size = no of nodes
*/

class Solution {
public:
    vector<vector<int>> arr;
    int ans = 0;
    int find_ans(int node, int parent){
        int initial_size = -1;
        bool flag = true;
        int total = 0;
        for(auto &neigh: arr[node]){
            if(neigh == parent)
                continue;
            int size = find_ans(neigh, node);

            if(initial_size == -1){
                initial_size = size;
            }
            if(size != initial_size){
                flag = false;
            }

            total += size;
        }

        if(flag)
            ans ++;

        return total+1;
        // Returning total nodes + root(1)
    }

    int countGoodNodes(vector<vector<int>>& edges) {
        int n = edges.size()+1;
        arr.resize(n);

        for(auto &it: edges){
            int x = it[0], y = it[1];
            arr[x].push_back(y);
            arr[y].push_back(x);
        }

        find_ans(0, -1);

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###