Count the Number of Good Nodes

Medium
1722.

Count the Number of Good Nodes

Count the Number of Good Nodes is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

An undirected tree has n nodes labelled 0 to n - 1 and is rooted at node 0. Its n - 1 edges are given in edges, each [ai, bi].

A node is good if all the subtrees rooted at its children have the same size (number of nodes). A leaf has no children, so it is always good.

Return the number of good nodes in the tree.

Example 1

Input
edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output
7
Explanation
Every node is good: node 0's two child subtrees both have 3 nodes, nodes 1 and 2 each have two leaf children, and the leaves 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
Nodes 1, 2 and 3 have children of different subtree sizes; the other six are good.

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
Only node 9 is not good: its children's subtrees have sizes 2 and 1.

Constraints

  • 2 <= n <= 10^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • the input is a valid tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} edges
 * @return {number}
 */
var countGoodNodes = function(edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count the Number of Good Nodes — Problem & Solution

Count the Number of Good Nodes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count the Number of Good Nodes is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An undirected tree has n nodes labelled 0 to n - 1 and is rooted at node 0. Its n - 1 edges are given in edges, each [ai, bi].

A node is good if all the subtrees rooted at its children have the same size (number of nodes). A leaf has no children, so it is always good.

Return the number of good nodes in the tree.

Example 1

Input: edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output: 7
Explanation: Every node is good: node 0's two child subtrees both have 3 nodes, nodes 1 and 2 each have two leaf children, and the leaves 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: Nodes 1, 2 and 3 have children of different subtree sizes; the other six are good.

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: Only node 9 is not good: its children's subtrees have sizes 2 and 1.

Constraints

  • 2 <= n <= 10^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • the input is a valid tree

Hints for Count the Number of Good Nodes

  1. Hint 1

    Whether a node is good depends only on the sizes of its children's subtrees, so compute every subtree size first.

  2. Hint 2

    Subtree sizes come from one bottom-up pass: process nodes children-before-parents and add each node's size to its parent's.

  3. Hint 3

    Then, for each node, compare the sizes of its children (all neighbours except the parent) with the first child's size.

How to solve Count the Number of Good Nodes

Compute every subtree size once, then check each node's children against each other. Each edge is looked at a constant number of times, so the whole thing is linear.

Approach

  1. Build adjacency lists and a BFS order from the root 0, recording each node's parent.
  2. Walk the BFS order backwards, adding size[u] to size[parent[u]] (every size starts at 1).
  3. For each node, scan its neighbours other than the parent; it is good if every such child has the same size as the first one (a leaf passes trivially).
  4. Return the count of good nodes.

Why it works

In reverse BFS order every child is finished before its parent, so size is exact when it is used. The goodness test is the definition applied directly.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The parent is a neighbour too — skip it, or the root's sizes get mixed with the whole tree's.
  • A node with a single child is always good: one size is trivially equal to itself.
  • Recursion over a long path can overflow the stack; the BFS order avoids it.

Reference solution

Python

from typing import List

def countGoodNodes(edges: List[List[int]]) -> int:
    n = len(edges) + 1
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    parent = [-2] * n
    parent[0] = -1
    order = [0]
    for u in order:
        for v in adj[u]:
            if parent[v] == -2:
                parent[v] = u
                order.append(v)
    size = [1] * n
    for u in reversed(order):
        if parent[u] >= 0:
            size[parent[u]] += size[u]
    good = 0
    for u in range(n):
        first = -1
        ok = True
        for v in adj[u]:
            if v == parent[u]:
                continue
            if first == -1:
                first = size[v]
            elif size[v] != first:
                ok = False
                break
        if ok:
            good += 1
    return good

Java

public static int countGoodNodes(int[][] edges) {
    int n = edges.length + 1;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    int[] parent = new int[n], order = new int[n], size = new int[n];
    Arrays.fill(parent, -2);
    Arrays.fill(size, 1);
    parent[0] = -1;
    int tail = 0;
    order[tail++] = 0;
    for (int h = 0; h < tail; h++) {
        int u = order[h];
        for (int v : adj.get(u)) if (parent[v] == -2) { parent[v] = u; order[tail++] = v; }
    }
    for (int t = n - 1; t > 0; t--) size[parent[order[t]]] += size[order[t]];
    int good = 0;
    for (int x = 0; x < n; x++) {
        int first = -1;
        boolean ok = true;
        for (int c : adj.get(x)) {
            if (c == parent[x]) continue;
            if (first == -1) first = size[c];
            else if (size[c] != first) { ok = false; break; }
        }
        if (ok) good++;
    }
    return good;
}

C++

int countGoodNodes(vector<vector<int>>& edges) {
    int n = edges.size() + 1;
    vector<vector<int>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    vector<int> parent(n, -2), size(n, 1), order;
    parent[0] = -1;
    order.push_back(0);
    for (size_t h = 0; h < order.size(); h++) {
        int u = order[h];
        for (int v : adj[u]) if (parent[v] == -2) { parent[v] = u; order.push_back(v); }
    }
    for (int t = n - 1; t > 0; t--) size[parent[order[t]]] += size[order[t]];
    int good = 0;
    for (int x = 0; x < n; x++) {
        int first = -1;
        bool ok = true;
        for (int c : adj[x]) {
            if (c == parent[x]) continue;
            if (first == -1) first = size[c];
            else if (size[c] != first) { ok = false; break; }
        }
        if (ok) good++;
    }
    return good;
}

JavaScript

var countGoodNodes = function(edges) {
    var n = edges.length + 1;
    var adj = [], parent = [], size = [];
    for (var i = 0; i < n; i++) { adj.push([]); parent.push(-2); size.push(1); }
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        adj[edges[e][1]].push(edges[e][0]);
    }
    parent[0] = -1;
    var order = [0];
    for (var h = 0; h < order.length; h++) {
        var u = order[h];
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (parent[v] === -2) { parent[v] = u; order.push(v); }
        }
    }
    for (var t = n - 1; t > 0; t--) size[parent[order[t]]] += size[order[t]];
    var good = 0;
    for (var x = 0; x < n; x++) {
        var first = -1, ok = true;
        for (var k = 0; k < adj[x].length; k++) {
            var c = adj[x][k];
            if (c === parent[x]) continue;
            if (first === -1) first = size[c];
            else if (size[c] !== first) { ok = false; break; }
        }
        if (ok) good++;
    }
    return good;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals