Watch 5 video solutions for Create Components With Same Value, a hard level problem involving Array, Math, Tree. This walkthrough by codingMohan has 1,334 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is an undirected tree with n nodes labeled from 0 to n - 1.
You are given a 0-indexed integer array nums of length n where nums[i] represents the value of the ith node. You are also 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 allowed to delete some edges, splitting the tree into multiple connected components. Let the value of a component be the sum of all nums[i] for which node i is in the component.
Return the maximum number of edges you can delete, such that every connected component in the tree has the same value.
Example 1:
Input: nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]] Output: 2 Explanation: The above figure shows how we can delete the edges [0,1] and [3,4]. The created components are nodes [0], [1,2,3] and [4]. The sum of the values in each component equals 6. It can be proven that no better deletion exists, so the answer is 2.
Example 2:
Input: nums = [2], edges = [] Output: 0 Explanation: There are no edges to be deleted.
Constraints:
1 <= n <= 2 * 104nums.length == n1 <= nums[i] <= 50edges.length == n - 1edges[i].length == 20 <= edges[i][0], edges[i][1] <= n - 1edges represents a valid tree.Problem Overview: You are given a tree where each node has a value. Remove edges so that every connected component has the same total value. The goal is to maximize the number of removed edges while keeping all resulting components with identical sums.
Approach 1: Depth First Search with Target Sum Enumeration (O(n * d) time, O(n) space)
The key observation: if the total sum of all node values is S, every component must sum to a divisor of S. Enumerate possible target sums and verify whether the tree can be split so each component equals that value. For each candidate target, run a Depth‑First Search on the tree to compute subtree sums. When a subtree sum reaches the target, treat it as a completed component and return 0 upward so the parent doesn't double count it. If any subtree exceeds the target, that configuration is invalid. The number of successful target partitions determines how many edges you can remove.
This works because every valid partition must align with subtree boundaries in a tree. DFS naturally aggregates values bottom‑up and lets you detect when a component sum matches the target.
Approach 2: Union-Find Component Aggregation (O(n α(n)) time, O(n) space)
An alternative model treats nodes as components and progressively merges them while tracking component sums using a Union-Find structure. Nodes are joined along edges while ensuring the combined sum does not exceed the chosen target value. When a merged component exactly equals the target sum, it becomes a finalized component and stops merging further. The disjoint-set structure allows efficient union and find operations while maintaining component sums.
This approach is less common for interviews but demonstrates how component constraints can be enforced dynamically with disjoint sets. It works well when you want explicit component tracking rather than recursive subtree accumulation.
Recommended for interviews: The DFS enumeration approach. It directly leverages tree properties and shows strong understanding of subtree aggregation. Start by computing the total sum, enumerate valid target sums, and validate each using DFS. The Union-Find approach is more specialized and rarely expected in interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Target Sum Enumeration | O(n * d) | O(n) | General case for trees. Best interview approach for validating equal-sum components. |
| Union-Find Component Aggregation | O(n α(n)) | O(n) | Useful when explicitly tracking merged components or experimenting with disjoint-set structures. |