Quick Overview

This question evaluates proficiency in tree traversal and aggregation techniques, specifically computing subtree sums using depth-first search while handling traversal state and constraints such as negative values and large n.

Compute subtree sums with tree DFS

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given an undirected tree with `n` nodes labeled `1..n` and `n-1` edges. The tree is rooted at node `1`. Each node `i` has an integer value `val[i]`. Return an array `subtreeSum[1..n]` where `subtreeSum[u]` is the sum of `val[x]` over all nodes `x` in the subtree of `u` (including `u`). Constraints: - `1 <= n <= 2e5` - Values can be negative. - The input is guaranteed to be a tree. Implement an `O(n)` solution using DFS.

Overview: This question evaluates proficiency in tree traversal and aggregation techniques, specifically computing subtree sums using depth-first search while handling traversal state and constraints such as negative values and large n.

Read the full Netflix Software Engineer interview experience this question came from

You are given an undirected tree with n nodes labeled from 1 to n, rooted at node 1. Each node i has an integer value val[i]. Return a list of length n where the element at index i-1 is the sum of values of all nodes in the subtree of node i, including node i itself. Your solution should run in O(n) time.

Constraints

  • 1 <= n <= 2 * 10^5
  • len(edges) == n - 1
  • -10^9 <= val[i] <= 10^9
  • The input graph is guaranteed to be a tree
  • Values may be negative

Examples

Input: (5, [(1, 2), (1, 3), (3, 4), (3, 5)], [4, 2, 1, 3, 5])

Expected Output: [15, 2, 9, 3, 5]

Explanation: Node 3 has subtree {3,4,5} with sum 1+3+5=9. Node 1 includes all nodes, so its sum is 15.

Input: (4, [(1, 2), (2, 3), (2, 4)], [1, -2, 4, -1])

Expected Output: [2, 1, 4, -1]

Explanation: Node 2 has subtree sum -2+4+(-1)=1, and node 1 has 1+1=2.

Hints

  1. Build an adjacency list for the tree, then run DFS from node 1 while tracking each node's parent.
  2. A node's subtree sum depends on its children, so compute results in postorder: children first, then parent.

Loading coding console...