Count the Number of Good Nodes - Solution & Explanation

Problem Overview: You are given an undirected tree with n nodes. A node is considered good if all of its child subtrees have the same size. Leaf nodes are automatically good because they have no children. The task is to count how many nodes satisfy this property.

Approach 1: DFS and Size Calculation (O(n) time, O(n) space)

The most direct strategy uses a single Depth-First Search traversal. Start from the root (usually node 0) and recursively compute the size of each subtree. For every node, iterate through its children and record the subtree size returned by DFS. If all recorded sizes are equal, the node is considered good. The subtree size for the current node is then 1 + sum(childSizes), which propagates upward in the recursion.

This works because DFS naturally processes children before their parent, so each node already knows the size of its descendants. During the DFS step you simply compare the first child subtree size with the rest. If any size differs, mark the node as not good. Each edge and node is visited once, giving O(n) time complexity with O(n) recursion stack and adjacency list storage.

Approach 2: DFS with Precomputed Subtree Sizes (O(n) time, O(n) space)

This variation separates the logic into two passes over the tree. The first DFS computes and stores the subtree size of every node in an array. The second traversal checks each node by iterating through its neighbors and considering only children (excluding the parent). Since subtree sizes are already known, you simply compare them directly without recomputation.

This approach improves code clarity in some languages such as Java or C#, where separating computation and validation can make recursion easier to maintain. The first pass fills a subtreeSize[] array, while the second pass checks whether all child subtree sizes match. The complexity remains O(n) time because each edge is processed a constant number of times, and O(n) space for the adjacency list and stored subtree sizes.

Both approaches rely on representing the input as an adjacency list and traversing it with DFS. The key observation is that subtree sizes fully determine whether a node qualifies as good. Once you know the size of every child subtree, verifying the condition becomes a simple equality check.

Recommended for interviews: The single-pass DFS that calculates subtree sizes while checking equality is the approach most interviewers expect. It demonstrates strong understanding of DFS traversal and recursive tree DP patterns. The two-pass version is still O(n) and easier to reason about, but the single-pass solution shows better algorithmic efficiency and control over recursion.