Watch 7 video solutions for Weighted Sum of a Tree, a medium level problem. This walkthrough by CodeSprint has 173 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array parent of length n representing a rooted tree with nodes labeled from 0 to n - 1.
The tree is rooted at node 0, so parent[0] = -1. For each node i where 1 <= i <= n - 1, parent[i] denotes the parent of node i.
You are also given an integer array nums of length n, where nums[i] denotes the value of node i.
The weight of a node i at depth d is nums[i] * (h - d + 1), where h is the height of the tree.
Return the sum of the weights of all nodes in the tree.
The depth of a node is the number of nodes on the path from the root to that node, inclusive, with the root having depth 1.
The height of the tree is the maximum depth among all nodes in the tree.
Example 1:
Input: parent = [-1,0,0,0,2,2], nums = [5,2,3,1,4,6]
Output: 37
Explanation:
The height of the tree is 3.
| Node | nums[i] |
Depth (d) |
Weight |
|---|---|---|---|
| 0 | 5 | 1 | 5 * (3 - 1 + 1) = 15 |
| 1 | 2 | 2 | 2 * (3 - 2 + 1) = 4 |
| 2 | 3 | 2 | 3 * (3 - 2 + 1) = 6 |
| 3 | 1 | 2 | 1 * (3 - 2 + 1) = 2 |
| 4 | 4 | 3 | 4 * (3 - 3 + 1) = 4 |
| 5 | 6 | 3 | 6 * (3 - 3 + 1) = 6 |
The sum of all node weights is 15 + 4 + 6 + 2 + 4 + 6 = 37.
Example 2:
Input: parent = [-1,0,1,2], nums = [1,2,3,4]
Output: 20
Explanation:
The height of the tree is 4.
| Node | nums[i] |
Depth (d) |
Weight |
|---|---|---|---|
| 0 | 1 | 1 | 1 * (4 - 1 + 1) = 4 |
| 1 | 2 | 2 | 2 * (4 - 2 + 1) = 6 |
| 2 | 3 | 3 | 3 * (4 - 3 + 1) = 6 |
| 3 | 4 | 4 | 4 * (4 - 4 + 1) = 4 |
The sum of all node weights is 4 + 6 + 6 + 4 = 20.
Constraints:
1 <= n <= 105n == parent.length == nums.lengthparent[0] == -10 <= parent[i] <= n - 1 for all i in [1, n - 1]1 <= nums[i] <= 106parent represents a valid tree rooted at node 0.Problem Overview: Given a tree where each edge has an associated weight, compute the total weighted sum of all paths from the root to every node. This is a fundamental tree traversal problem that tests your ability to accumulate values during traversal.
Approach 1: Recursive DFS (O(n) time, O(h) space)
Depth-first search is the most intuitive way to solve this. Start at the root with a cumulative sum of 0. For each child, add the edge weight to the current sum and recurse. When you reach a leaf, add the accumulated sum to the total. This works because you're carrying the path sum down the recursion stack. The time complexity is O(n) since you visit every node once, but the space complexity depends on the tree height h, which can be O(n) for skewed trees and risks stack overflow.
Approach 2: Iterative BFS (O(n) time, O(w) space)
Breadth-First Search processes nodes level by level using a queue. Initialize a queue with the root and its cumulative weight (0). While the queue isn't empty, pop a node, add its cumulative weight to the total, and push each child with the updated cumulative weight (parent's weight + edge weight). This avoids recursion entirely and is more robust for deep trees. The key insight is that each node's cumulative weight depends only on its parent's value, so you can compute it on the fly during traversal. Time is O(n), space is O(w) where w is the maximum width of the tree—typically much smaller than n.
Recommended for interviews: Interviewers expect you to implement the BFS approach because it demonstrates iterative thinking and avoids recursion depth issues. While DFS shows you understand recursion, BFS is often preferred in production code for tree traversal problems due to its predictable memory usage. Start with DFS to show you can reason about recursion, then optimize to BFS for a stronger solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS | O(n) | O(h) | When tree is balanced and recursion depth is safe |
| Iterative BFS | O(n) | O(w) | General case; avoids recursion; handles deep trees |