Find Number of Coins to Place in Tree Nodes - Video Solutions

Problem Overview: You are given a tree where each node has an integer value. For every node, compute how many coins should be placed on it based on the maximum product of any three values inside that node's subtree. If the subtree has fewer than three nodes, the result is 1. The challenge is efficiently aggregating subtree values while traversing the tree.

Approach 1: DFS with Sorting (O(n log k) time, O(n) space)

Run a Depth-First Search from the root and collect values from each subtree. At every node, maintain a list of candidate values from its children plus its own value. Sort the collected values and compute the maximum product using the largest three numbers or two smallest negatives with the largest positive. Since only a few extreme values matter, you typically keep the top three maximum values and bottom two minimum values after sorting. The product is assigned to the node if the subtree has at least three nodes; otherwise return 1. This approach is straightforward to implement and works well because the candidate list stays very small.

Approach 2: DFS with Priority Queue (O(n log k) time, O(n) space)

This variant replaces sorting with heaps. During the tree traversal, each DFS call maintains two structures: a max-oriented structure for the largest values and a min-oriented structure for the smallest negatives. While merging child results, push values into the heaps and keep only the few extremes required to evaluate the product. After gathering candidates for a node, compute the best product using either the three largest numbers or the combination of two smallest negatives and the largest positive. Using a priority queue avoids repeated sorting and keeps updates efficient when merging multiple children.

Recommended for interviews: The DFS aggregation approach with tracked extremes is what interviewers expect. It shows you understand subtree dynamic programming and how to propagate only the necessary information upward. A naive solution that collects all subtree values demonstrates the idea, but maintaining only the top three maximums and bottom two minimums proves you can optimize both time and memory.