Is Weighted Sum of a Tree easy or hard?

It's rated Medium on FleetCode with a 41.7% acceptance rate. It's not trivial because you need to handle edge weights correctly, but it's manageable if you're comfortable with standard tree traversals.

Weighted Sum of a Tree Python/Java solution

You can implement BFS in Python using collections.deque and in Java using LinkedList or ArrayDeque. The logic remains identical across languages: push root with weight 0, pop nodes, accumulate weights, push children with updated weights.

How to solve Weighted Sum of a Tree in O(n)?

Use BFS or DFS traversal. Maintain a cumulative weight for each node as parent weight plus edge weight. Add these cumulative weights as you visit each node. Both approaches run in O(n) time.

What is the best approach for Weighted Sum of a Tree?

The best approach is iterative Breadth-First Search (BFS). It runs in O(n) time and uses O(w) space, where w is the maximum width of the tree. BFS avoids recursion depth issues and is straightforward to implement with a queue.

Is Weighted Sum of a Tree asked at Google/Amazon/Meta?

Yes, tree traversal problems like this are common at top tech companies including Google, Amazon, and Meta. They test your understanding of graph traversal and handling weighted edges.

What data structure is used in Weighted Sum of a Tree?

A queue is used for iterative BFS traversal. Alternatively, recursion uses an implicit stack for DFS. The tree itself is typically represented using adjacency lists or node objects with children.

What is the time complexity of Weighted Sum of a Tree?

The optimal time complexity is O(n), where n is the number of nodes in the tree. You must visit every node exactly once to compute the cumulative weighted sum.

Description Hints 2 Solution Video 10:00

4015. Weighted Sum of a Tree

Medium42.3% acceptance

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 <= 10⁵
n == parent.length == nums.length
parent[0] == -1
0 <= parent[i] <= n - 1 for all i in [1, n - 1]
1 <= nums[i] <= 10⁶
The input is generated such that the array parent represents a valid tree rooted at node 0.

Topics

Hints open one at a time

Hint 1

Build the tree and traverse it from the root to determine the depth of every node and the height h.

Hint 2

Once h is known, calculate and sum nums[i] * (h - depth[i] + 1) for every node i.

10:00

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def weightedSum(self, parent: list[int], nums: list[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[-1,0,0,0,2,2]
[5,2,3,1,4,6]

Input

[-1,0,1,2]
[1,2,3,4]

Your code is saved on this device.Solution