Skip to main content
Talentd

Find Number of Coins to Place in Tree Nodes - Solution & Explanation

HardDynamic ProgrammingTreeDepth-First SearchSorting29 min readAsked at: Amazon
Practice this problem

Problem Statement

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:

  • If size of the subtree of node i is less than 3, place 1 coin.
  • Otherwise, place an amount of coins equal to the maximum product of cost values assigned to 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 * 104
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • cost.length == n
  • 1 <= |cost[i]| <= 104
  • The input is generated such that edges represents a valid tree.

Approach Overview

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.

Approach 1: DFS with Sorting

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: DFS with Priority Queue

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.

Code

C++PythonJava

C++

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 3: DFS + Sorting

According to the problem description, there are two situations for the number of coins placed at each node a:

  • If the number of nodes in the subtree corresponding to node a is less than 3, then place 1 coin;
  • If the number of nodes in the subtree corresponding to node 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]:

  • If 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;
  • If 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
DFS with Sorting

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.

DFS with Priority Queue

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.

DFS + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with SortingO(n log k)O(n)Simple implementation when only a few extreme values are kept per subtree
DFS with Priority QueueO(n log k)O(n)Useful when merging many child subtrees and you want structured access to extremes

Video Solution

FIND NUMBER OF COINS TO PLACE IN BINARY TREE NODES | LEETCODE 2973 | PYTHON DFS + HEAP SOLUTION • Cracking FAANG • 1,574 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Find Number of Coins to Place in Tree Nodes easy or hard?
The problem is classified as Hard on LeetCode because it combines tree traversal with careful value aggregation. The main difficulty comes from recognizing that only a few extreme values in each subtree affect the maximum product. Once that insight is clear, the implementation becomes a manageable DFS dynamic programming pattern.
Find Number of Coins to Place in Tree Nodes Python/Java solution
Python and Java solutions typically implement DFS over the adjacency list and return a small list of candidate values for each subtree. After combining child results, the algorithm computes the best product and stores it for the current node. The same logic translates directly to C++, Java, and other languages.
How to solve Find Number of Coins to Place in Tree Nodes in O(n)?
Traverse the tree using DFS and compute results bottom‑up. Each node returns a small set of candidate values from its subtree: the three largest and two smallest numbers. Using these extremes, compute the maximum product either from the three largest values or from two negatives and the largest positive. Propagate the reduced candidate set to the parent so the traversal stays linear.
What is the best approach for Find Number of Coins to Place in Tree Nodes?
The most effective approach is a DFS-based subtree dynamic programming solution. During traversal, keep only the top three maximum values and bottom two minimum values from each subtree. These extremes are enough to compute the maximum product of three numbers. The solution runs in O(n) traversal time with small constant factors for maintaining candidates.
Is Find Number of Coins to Place in Tree Nodes asked at Google/Amazon/Meta?
Tree DP and subtree aggregation problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. Variants often involve computing metrics over subtrees or propagating partial results during DFS. Understanding how to keep only necessary extremes is a common optimization pattern tested in these interviews.
What data structure is used in Find Number of Coins to Place in Tree Nodes?
The core structures are adjacency lists for the tree and recursion or stacks for DFS traversal. Many implementations also use arrays or small lists to track extreme values, while alternative versions use heaps or priority queues to maintain the largest and smallest numbers efficiently.
What is the time complexity of Find Number of Coins to Place in Tree Nodes?
The typical optimized solution runs in O(n) DFS traversal with small additional operations per node. When sorting or heap operations are used to maintain candidate values, the complexity is often described as O(n log k) where k is the small number of tracked values (usually ≤5). Space complexity is O(n) due to recursion stack and adjacency lists.

Ready to solve this problem?

Practice Find Number of Coins to Place in Tree Nodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Collect Coins in a Tree

Next

Find the Maximum Sum of Node Values