Count the Number of Good Nodes - Practice Coding Problems

Count the Number of Good Nodes - Problem

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.

Input & Output

Example 1 — Balanced Tree

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

› Output: 7

💡 Note: Tree rooted at 0 with balanced subtrees. Node 0 has children 1,2 with subtree sizes 3,3 (equal). Node 1 has children 3,4 with sizes 1,1. Node 2 has children 5,6 with sizes 1,1. All leaf nodes (3,4,5,6) have no children. All 7 nodes are good.

Example 2 — Unbalanced Tree

$ Input: edges = [[0,1],[1,2],[2,3],[3,4]]

› Output: 5

💡 Note: Linear tree: 0-1-2-3-4. Each node has at most one child, so all nodes are good (single child always has 'equal' sizes with itself). Total: 5 good nodes.

Example 3 — Single Node

$ Input: edges = []

› Output: 1

💡 Note: Tree with only node 0. Since it has no children, it's considered good. Total: 1 good node.

Constraints

1 ≤ n ≤ 10⁵
edges.length == n - 1
edges[i].length == 2
0 ≤ a_i, b_i < n
The input represents a valid tree

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Undirected tree with edges defining parent-child relationships

Check Each Node

For each node, compare subtree sizes of all children

Count Good Nodes

Nodes with equal child subtree sizes are 'good'

Key Takeaway

🎯 Key Insight: Use DFS to calculate subtree sizes once and check equality of children's sizes

Asked in

G Google 25 f Meta 18 a Amazon 15

The key insight is to use DFS to calculate subtree sizes in a single traversal. A node is good if all its children have subtrees of equal size. The optimal approach uses post-order DFS to compute sizes bottom-up. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS	O(n)	O(n)	Single DFS pass calculating subtree sizes and counting good nodes simultaneously
Brute Force DFS	O(n²)	O(n)	For each node, calculate subtree sizes of all children separately

Optimized DFS — Algorithm Steps

Build adjacency list from edges
Start DFS from root (node 0)
For each node, recursively calculate subtree sizes of children
Check if all children have equal subtree sizes
Return subtree size and count good nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Traversal

Visit each node once in post-order

Calculate Sizes

Return subtree size from each child

Check & Count

Compare child sizes and count good nodes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 100005

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
int goodCount;
int n;

int dfs(int node, int parent) {
    int children[MAX_N];
    int childCount = 0;
    
    for (int i = 0; i < graphSize[node]; i++) {
        int child = graph[node][i];
        if (child != parent) {
            children[childCount++] = child;
        }
    }
    
    if (childCount == 0) {
        goodCount++;
        return 1;
    }
    
    int subtreeSizes[MAX_N];
    int totalSize = 1;
    
    for (int i = 0; i < childCount; i++) {
        int childSize = dfs(children[i], node);
        subtreeSizes[i] = childSize;
        totalSize += childSize;
    }
    
    int uniqueSizes[MAX_N];
    int uniqueCount = 0;
    
    for (int i = 0; i < childCount; i++) {
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (uniqueSizes[j] == subtreeSizes[i]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            uniqueSizes[uniqueCount++] = subtreeSizes[i];
        }
    }
    
    if (uniqueCount <= 1) {
        goodCount++;
    }
    
    return totalSize;
}

int solution(int edges[][2], int edgeCount) {
    if (edgeCount == 0) return 1;
    
    n = edgeCount + 1;
    goodCount = 0;
    
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
    }
    
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u][graphSize[u]++] = v;
        graph[v][graphSize[v]++] = u;
    }
    
    dfs(0, -1);
    return goodCount;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int edges[MAX_N][2];
    int edgeCount = 0;
    
    if (strcmp(line, "[]\n") == 0) {
        printf("1\n");
        return 0;
    }
    
    char *ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgeCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            edges[edgeCount][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            edgeCount++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(edges, edgeCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single DFS traversal visits each node exactly once

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to tree height and adjacency list storage

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler