Katkat
Back

Compute subtree sums with tree DFS

NetflixSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.