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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of Good Nodes

Difficulty: Medium

Problem Description

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 subtrees rooted at its children have the same size. Return the number of good nodes in the given tree.

Key Insights

  • A node is considered good if all its children (subtrees) have the same number of nodes.
  • A depth-first search (DFS) approach can be used to traverse the tree and calculate the size of each node's subtree.
  • While calculating subtree sizes, maintain a count of how many times each size occurs among the children of a node.
  • A node is good if there is only one unique size among its children's subtrees.

Space and Time Complexity

Time Complexity: O(n) - Each node and edge is visited once during the DFS traversal.
Space Complexity: O(n) - The space is used for the adjacency list representation of the tree and the recursion stack.

Solution

To solve the problem, we can represent the tree using an adjacency list. We will use a DFS approach to traverse the tree starting from the root (node 0). For each node, we will calculate the size of its subtree, and maintain a frequency count of the sizes of its children's subtrees. If there is only one unique size, the node is considered good.

  1. Build the tree using an adjacency list from the edges.
  2. Implement a recursive DFS function that calculates the size of each subtree.
  3. During the DFS, keep track of the count of subtree sizes for each node.
  4. For each node, check if all children's subtree sizes are the same.
  5. Return the count of good nodes.

Code Solutions

def countGoodNodes(edges):
    from collections import defaultdict
    
    # Build the tree as an adjacency list
    tree = defaultdict(list)
    for a, b in edges:
        tree[a].append(b)
        tree[b].append(a)

    good_node_count = 0
    
    def dfs(node, parent):
        nonlocal good_node_count
        subtree_size = 1
        child_sizes = []
        
        for neighbor in tree[node]:
            if neighbor == parent:  # Avoid going back to the parent
                continue
            size = dfs(neighbor, node)
            child_sizes.append(size)
            subtree_size += size
        
        # Check if all child sizes are the same
        if len(set(child_sizes)) <= 1:
            good_node_count += 1
        
        return subtree_size

    dfs(0, -1)  # Start DFS from the root (node 0)
    
    return good_node_count + 1  # Include the root as a good node

# Example usage
print(countGoodNodes([[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]))  # Output: 7
← Back to All Questions