Maximum Good Subtree Score

Maximum Good Subtree Score

What is this problem about?

The Maximum Good Subtree Score coding problem operates on a rooted tree where each node has a value. A "good" subtree rooted at a node is one where no digit (0-9) appears more than once across all node values in the subtree. You want to assign to each node a score — the sum of values of all nodes in its largest good subtree — and maximize this score. This combines tree DFS with bitmask DP to track digit usage efficiently.

Why is this asked in interviews?

Infosys and other companies present this problem to test advanced tree DP skills combined with bitmask representation. It requires candidates to think about subtree state propagation where the state is a set (of digits used), which maps naturally to a bitmask. The combination of Depth-First Search, Bit Manipulation, and Dynamic Programming in a tree context is a hallmark of hard interview problems at top companies.

Algorithmic pattern used

The solution uses DFS with bitmask DP. For each node, compute the bitmask of digits in the node's own value. During DFS, when merging children results, you combine bitmasks using OR and check for conflicts (overlapping digits). You maintain, for each subtree, the maximum sum achievable for each valid digit-bitmask. The key DP transition: for a node with digit-mask d, merge child subtrees greedily by combining non-conflicting masks. The space is O(n * 2^10) in the worst case but manageable with pruning.

Example explanation

Tree: root=0 (value 12), child=1 (value 34)

• Node 1 digit mask: digits {3,4} → mask = 0b11000 (bits 3,4)
• Node 0 digit mask: digits {1,2} → mask = 0b110 (bits 1,2)
• Combining: 0b110 | 0b11000 = 0b11110, no overlap. Good subtree sum = 12 + 34 = 46.
• Score for root = 46.

If child had value 21 instead (digits {2,1}), combining with root's mask {1,2} gives overlap → not a good subtree. Root's best good subtree is just itself: score = 12.

Common mistakes candidates make

• Not handling multi-digit node values: A node with value 123 uses digits 1, 2, and 3. Forgetting to extract all digits from a value creates wrong masks.
• Assuming subtree = all descendants: A "good subtree" might not include all descendants if some conflict. The DP must track partial inclusion.
• Integer overflow on sums: Node values can be large; use 64-bit integers for sums.

Interview preparation tip

For the Array Bitmask Depth-First Search Bit Manipulation Dynamic Programming Tree interview pattern, practice digit-mask extraction as a utility first. Then solve simpler bitmask DP on trees (like path with unique characters) before tackling this problem. The core skill is merging child DP states while checking bitmask compatibility.