# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/graph/dfs-bfs/3249.-count-the-number-of-good-nodes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.