You are given 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.
You are also given a 0-indexed integer array cost of length n, where cost[i] is the cost assigned to the ith node.
You need to place some coins on every node of the tree. The number of coins to be placed at node i can be calculated as:
i is less than 3, place 1 coin.3 distinct nodes in the subtree of node i. If this product is negative, place 0 coins.Return an array coin of size n such that coin[i] is the number of coins placed at node i.
Example 1:
Input: edges = [[0,1],[0,2],[0,3],[0,4],[0,5]], cost = [1,2,3,4,5,6] Output: [120,1,1,1,1,1] Explanation: For node 0 place 6 * 5 * 4 = 120 coins. All other nodes are leaves with subtree of size 1, place 1 coin on each of them.
Example 2:
Input: edges = [[0,1],[0,2],[1,3],[1,4],[1,5],[2,6],[2,7],[2,8]], cost = [1,4,2,3,5,7,8,-4,2] Output: [280,140,32,1,1,1,1,1,1] Explanation: The coins placed on each node are: - Place 8 * 7 * 5 = 280 coins on node 0. - Place 7 * 5 * 4 = 140 coins on node 1. - Place 8 * 2 * 2 = 32 coins on node 2. - All other nodes are leaves with subtree of size 1, place 1 coin on each of them.
Example 3:
Input: edges = [[0,1],[0,2]], cost = [1,2,-2] Output: [0,1,1] Explanation: Node 1 and 2 are leaves with subtree of size 1, place 1 coin on each of them. For node 0 the only possible product of cost is 2 * 1 * -2 = -4. Hence place 0 coins on node 0.
Constraints:
2 <= n <= 2 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < ncost.length == n1 <= |cost[i]| <= 104edges represents a valid tree.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.
The idea is to use Depth First Search (DFS) to calculate the size of each subtree and find the maximum cost product using sorting for the top 3 values.
We can use a DFS traversal to calculate the size of the subtree for each node. If the size is less than 3, place 1 coin. Otherwise, collect all costs in the given subtree, sort the costs, and compute the maximum product of the top 3 values. This approach ensures optimized computation by leveraging the sorting step on potentially large subtrees.
This C solution uses DFS to traverse the tree and calculate subtree sizes. It maintains an adjacency list in a matrix format, uses a simple DFS for traversal, and calculates the number of coins to be placed using a sorted list of subtree costs. It sorts the subtree costs and computes the maximum product for valid nodes.
Time Complexity: O(n log n) due to sorting of subtree costs in each DFS call.
Space Complexity: O(n) for storing tree adjacency information and results.
This approach uses a priority queue (or max-heap) to track the top 3 largest values in each node's subtree. During the DFS traversal, instead of sorting the entire subtree costs, we maintain the top 3 maximum costs in the heap. This approach is slightly more efficient in scenarios where sorting can be avoided.
The C++ solution uses a priority queue (max-heap) to track the largest three elements in the subtree, reducing the need to sort the entire subtree list. This method is comparatively optimized for larger trees where subtree sizes can be unwieldy.
Time Complexity: O(n log 3) = O(n), because we keep only 3 elements in the priority queue.
Space Complexity: O(n), since we maintain adjacency lists and results arrays.
According to the problem description, there are two situations for the number of coins placed at each node a:
a is less than 3, then place 1 coin;a is greater than or equal to 3, then we need to take out 3 different nodes from the subtree, calculate the maximum value of their cost product, and then place the corresponding number of coins at node a. If the maximum product is negative, place 0 coins.The first situation is relatively simple, we just need to count the number of nodes in the subtree of each node during the traversal.
For the second situation, if all costs are positive, we should take the 3 nodes with the largest costs; if there are negative costs, we should take the 2 nodes with the smallest costs and the 1 node with the largest cost. Therefore, we need to maintain the smallest 2 costs and the largest 3 costs in each subtree.
We first construct the adjacency list g based on the given two-dimensional array edges, where g[a] represents all neighbor nodes of node a.
Next, we design a function dfs(a, fa), which returns an array res, which stores the smallest 2 costs and the largest 3 costs in the subtree of node a (may not be 5).
In the function dfs(a, fa), we add the cost cost[a] of node a to the array res, and then traverse all neighbor nodes b of node a. If b is not the parent node fa of node a, then we add the result of dfs(b, a) to the array res.
Then, we sort the array res, and then calculate the number of coins placed at node a based on the length m of the array res, and update ans[a]:
m \ge 3, then the number of coins placed at node a is max(0, res[m - 1] times res[m - 2] times res[m - 3], res[0] times res[1] times res[m - 1]), otherwise the number of coins placed at node a is 1;m > 5, then we only need to keep the first 2 elements and the last 3 elements of the array res.Finally, we call the function dfs(0, -1), and return the answer array ans.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of nodes.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| DFS with Sorting | Time Complexity: O(n log n) due to sorting of subtree costs in each DFS call. |
| DFS with Priority Queue | Time Complexity: O(n log 3) = O(n), because we keep only 3 elements in the priority queue. |
| DFS + Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Sorting | O(n log k) | O(n) | Simple implementation when only a few extreme values are kept per subtree |
| DFS with Priority Queue | O(n log k) | O(n) | Useful when merging many child subtrees and you want structured access to extremes |
FIND NUMBER OF COINS TO PLACE IN BINARY TREE NODES | LEETCODE 2973 | PYTHON DFS + HEAP SOLUTION • Cracking FAANG • 1,553 views views
Watch 5 more video solutions →Practice Find Number of Coins to Place in Tree Nodes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor