Optimal Subtree Sum — Problem Statement & Solution Guide

TreesHardDP on Trees

TimeO(N)

SpaceO(N)

Problem Description

Given a tree with nodes having unique identifiers and non-negative integer weights, find the maximum sum of weights that can be obtained by removing a subset of nodes such that the remaining nodes form a connected subtree.

DSA Pattern Breakdown

"Optimal Subtree Sum"

hard

WHY DOES IT MATTER?

Tree‑DP is a cornerstone pattern for any problem that asks for an optimal property of a connected substructure in a hierarchy. Recognizing that the optimal solution can be built from optimal solutions of sub‑trees eliminates exponential enumeration and unlocks linear‑time solutions.

OPTIMIZATION CHALLENGE

The key insight is the "positive‑child‑pruning" rule: during a post‑order walk, only propagate child sums that are greater than zero. This single conditional cuts the combinatorial explosion and collapses the problem to O(N) time.

REAL-WORLD CONNECTION

Think of a corporate org chart where each employee contributes a profit margin. To find the most profitable division that remains a contiguous reporting line, you aggregate positive contributions from sub‑teams and drop loss‑making branches – exactly the DP logic used in this problem.

During an interview, compute dp[node] on the fly while returning from recursion; keep a global variable for the maximum seen so far. This avoids a second pass and keeps the code concise – a trick interviewers love to see.

COMPLEXITY AT A GLANCE

⏱ Time:O(N)

💾 Space:O(N)

Core Theory — Why This Approach?

The optimal subtree‑sum problem is a classic example of tree‑DP (dynamic programming on trees). By rooting the tree arbitrarily, we can compute for each node the maximum sum of a connected sub‑tree that includes that node and stays entirely within its descendant sub‑tree. The recurrence is simple: start with the node’s own weight, then add the contribution of each child only if that child’s best‑including‑child sum is positive. This greedy‑like addition works because any negative contribution would only decrease the total of a connected component that must contain the parent, so it is optimal to discard that branch. The global optimum is the maximum value observed among all dp[node] values, because the best connected subtree may be rooted anywhere, not necessarily at the original root.

A naïve brute‑force approach would enumerate every subset of nodes, verify connectivity, and compute the sum – an O(2^N) explosion that collapses even for modest N (N ≤ 20). Such exponential blow‑up is unacceptable for the typical constraints of N up to 10^5 or more, which appear in real‑world code‑challenge platforms. The tree‑DP paradigm reduces the problem to a single linear pass: a post‑order traversal computes each dp in O(1) time using already‑computed child values, yielding an overall O(N) time algorithm with O(N) auxiliary space for the recursion stack or an explicit stack. This optimal paradigm leverages the hierarchical nature of trees, turning a combinatorial search into a deterministic aggregation.

Interview Questions on This Problem

Q1How would you modify the DP solution if the tree is given as an undirected graph without a predefined root?

Pick any node as a temporary root (e.g., node 1) and run a DFS to establish parent‑child relationships. The DP recurrence works unchanged because the tree structure is preserved; after the first pass you can also run a second pass (rerooting) if you need dp values for every possible root, but for the maximum subtree sum a single rooted pass suffices.

Q2Explain why adding only positive child contributions guarantees the optimal connected subtree that contains the current node.

A connected subtree that includes the current node must either take the entire child sub‑tree or discard it; taking a child sub‑tree with a negative total would strictly lower the sum while still preserving connectivity, so the optimal choice is to exclude any child whose best‑including‑child sum is ≤ 0. This local optimality extends globally because the tree has no cycles, preventing any later decision from re‑introducing the discarded negative contribution.

Q3In a distributed system where each service node reports a health score, how could the optimal subtree‑sum algorithm help you isolate the healthiest cluster?

Model services as tree nodes with health scores (which may be negative for degraded services). Running the DP computes the maximum‑weight connected cluster, i.e., the healthiest contiguous group of services. This informs automated fail‑over or scaling decisions by pinpointing the sub‑system that maximizes overall health while remaining internally reachable.

Examples

Example 1

Input

Example 1: 
 1
 1 2
 2 3
 3 4
 4 5

Output: 28
Explanation: Remove nodes 2 and 4 to get a connected subtree with sum 28.

Output

Explanation: Step-by-step: 1. Start with the original tree. 2. Remove node 2, which breaks the connected subtree. 3. Remove node 4, which breaks the connected subtree. 4. Remove nodes 2 and 4, which results in a connected subtree with sum 28.

Example 2

Input

Example 2: 
 1
 1 2
 2 3
 3 4
 4 5

Output: 22
Explanation: Remove nodes 2 and 5 to get a connected subtree with sum 22.

Output

Explanation: Step-by-step: 1. Start with the original tree. 2. Remove node 2, which breaks the connected subtree. 3. Remove node 5, which breaks the connected subtree. 4. Remove nodes 2 and 5, which results in a connected subtree with sum 22.

Constraints

1 <= number of nodes <= 100
Each node has a unique identifier
Weights are non-negative integers between 0 and 10^6

Optimal Approach & Strategy

Root the tree and perform a single post‑order DFS, adding only positive child dp values to each node’s weight; keep the global maximum dp as the result – O(N) time.

Brute Force Approach

Enumerate every subset of nodes, check if the subset forms a connected subtree, and compute its weight sum – O(2^N) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N)

function solution(graph) {
   const visited = new Set();
   let maxSum = 0;
   function dfs(node, parent) {
      visited.add(node);
      let sum = graph[node].weight;
      for (const neighbor of graph[node].neighbors) {
         if (neighbor !== parent && !visited.has(neighbor)) {
            sum += dfs(neighbor, node);
         }
      }
      return sum;
   }
   for (const node in graph) {
      if (!visited.has(node)) {
         maxSum = Math.max(maxSum, dfs(node, null));
      }
   }
   return maxSum;
}

class Solution {
   public:
   int solution(unordered_map<string, Node> graph) {
      unordered_set<string> visited;
      int maxSum = 0;
      for (auto node : graph) {
         if (visited.find(node.first) == visited.end()) {
            maxSum = max(maxSum, dfs(node.first, nullptr, graph, visited));
         }
      }
      return maxSum;
   }
   private:
   int dfs(string node, string parent, unordered_map<string, Node> graph, unordered_set<string> visited) {
      visited.insert(node);
      int sum = graph[node].weight;
      for (auto neighbor : graph[node].neighbors) {
         if (neighbor != parent && visited.find(neighbor) == visited.end()) {
            sum += dfs(neighbor, node, graph, visited);
         }
      }
      return sum;
   }
}

class Solution {
   public int solution(Map<String, Node> graph) {
      Set<String> visited = new HashSet<>();
      int maxSum = 0;
      for (String node : graph.keySet()) {
         if (!visited.contains(node)) {
            maxSum = Math.max(maxSum, dfs(node, null, graph, visited));
         }
      }
      return maxSum;
   }
   private int dfs(String node, String parent, Map<String, Node> graph, Set<String> visited) {
      visited.add(node);
      int sum = graph.get(node).weight;
      for (String neighbor : graph.get(node).neighbors) {
         if (!neighbor.equals(parent) && !visited.contains(neighbor)) {
            sum += dfs(neighbor, node, graph, visited);
         }
      }
      return sum;
   }
}

def solution(graph):
   visited = set()
   max_sum = 0
   def dfs(node, parent):
      visited.add(node)
      sum = graph[node]['weight']
      for neighbor in graph[node]['neighbors']:
         if neighbor != parent and neighbor not in visited:
            sum += dfs(neighbor, node)
      return sum
   for node in graph:
      if node not in visited:
         max_sum = max(max_sum, dfs(node, None))
   return max_sum

function solution(graph) {
   const visited = new Set();
   let maxSum = 0;
   function dfs(node, parent) {
      visited.add(node);
      let sum = graph[node].weight;
      for (const neighbor of graph[node].neighbors) {
         if (neighbor !== parent && !visited.has(neighbor)) {
            sum += dfs(neighbor, node);
         }
      }
      return sum;
   }
   for (const node in graph) {
      if (!visited.has(node)) {
         maxSum = Math.max(maxSum, dfs(node, null));
      }
   }
   return maxSum;
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Optimal Subtree Sum Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Trees

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Optimal Subtree Sum — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor