We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count the Number of Good Nodes

Number: 3486

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an undirected tree with n nodes (labeled from 0 to n - 1) and rooted at node 0, and provided with an array of edges, count the number of nodes that are "good". A node is considered good if the sizes of the subtrees rooted at each of its children are all identical. (A leaf node or a node with a single child is trivially good.) The goal is to return the total count of such good nodes.

Key Insights

  • Compute the size of each subtree using Depth-First Search (DFS).
  • For each node, gather the sizes of its children subtrees.
  • A node with 0 or 1 child is always good since there is no discrepancy in subtree sizes.
  • For nodes with two or more children, verify that all children subtrees have the same computed size.
  • Use an undirected tree representation but avoid re-visiting the parent node during DFS.

Space and Time Complexity

Time Complexity: O(n) – Each node is visited once during the DFS. Space Complexity: O(n) – This includes the space for the recursion stack and the tree representation (adjacency list).

Solution

We approach the problem by first constructing an adjacency list from the given edges. Then, using DFS starting from the root (node 0), we compute the size of each subtree recursively. As we compute the size for a node, we maintain a list of the sizes of the subtrees for its children. After processing a node’s children, if there are at most one child, the node is automatically good. Otherwise, we check if all the values in that list are identical. If they are, we mark the node as good and increment our counter. Finally, we return the total count of good nodes.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java. Each solution uses DFS to compute subtree sizes and count the good nodes, with detailed in-line comments for clarity.

def count_good_nodes(n, edges):
    from collections import defaultdict
    # Build the tree as an adjacency list
    tree = defaultdict(list)
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)

    good_count = 0

    # DFS function to compute subtree sizes and count good nodes
    def dfs(node, parent):
        nonlocal good_count
        subtree_size = 1
        child_sizes = []  # List to store sizes of each child's subtree

        # Process all children (neighbors except parent)
        for neighbor in tree[node]:
            if neighbor == parent:
                continue
            child_size = dfs(neighbor, node)
            child_sizes.append(child_size)
            subtree_size += child_size

        # A node with 0 or 1 child is good by default
        if len(child_sizes) < 2:
            good_count += 1
        else:
            # Check if all child's subtree sizes are equal
            if all(size == child_sizes[0] for size in child_sizes):
                good_count += 1

        return subtree_size

    dfs(0, -1)
    return good_count


# Example Usage:
edges1 = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
print(count_good_nodes(7, edges1))  # Output: 7
← Back to All Questions