Weighted Sum of a Tree - Solution & Explanation

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.