Maximum Score After Applying Operations on a Tree - Solution & Explanation

Q: Is Maximum Score After Applying Operations on a Tree easy or hard?

The problem is typically classified as Medium difficulty. The challenge is recognizing that maximizing score is equivalent to minimizing the value that must remain in the tree. Once that insight is clear, a single DFS with tree dynamic programming solves it in linear time.

Q: Maximum Score After Applying Operations on a Tree Python/Java solution

In Python or Java, construct the tree using an adjacency list and run a DFS that returns the required value for each subtree. Maintain the total sum of node values, compute subtree requirements with min(nodeValue, sum(childResults)), and subtract the root requirement from the total to get the maximum score.

Q: How to solve Maximum Score After Applying Operations on a Tree in O(n)?

Build an adjacency list and run a post‑order DFS from the root. For leaf nodes, return their value since removing them would break the path constraint. For internal nodes, compute the sum of required values from children and return min(nodeValue, childSum). Track the total sum of all nodes and subtract the root’s required value to get the maximum score.

Q: What is the best approach for Maximum Score After Applying Operations on a Tree?

The optimal approach uses DFS with tree dynamic programming. Traverse the tree bottom‑up and compute the minimum value that must remain in each subtree to keep every root‑to‑leaf path non‑zero. For each node, return min(nodeValue, sum of required values from children). The final score equals total node values minus the required value at the root. This runs in O(n) time.

Q: Is Maximum Score After Applying Operations on a Tree asked at Google/Amazon/Meta?

Problems combining tree traversal and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require computing optimal values along root‑to‑leaf paths or subtree decisions are common in senior‑level coding interviews.

Q: What data structure is used in Maximum Score After Applying Operations on a Tree?

The solution uses an adjacency list to represent the tree and Depth‑First Search for traversal. The algorithm also applies dynamic programming on the tree structure, where each node stores the minimum value required to preserve valid root‑to‑leaf paths.

Q: What is the time complexity of Maximum Score After Applying Operations on a Tree?

The optimal DFS solution runs in O(n) time where n is the number of nodes in the tree. Each node and edge is visited once during traversal. Space complexity is O(n) due to the adjacency list and recursion stack (or explicit stack in the iterative version).

MediumDynamic Programming Tree Depth-First Search27 min readAsked at: Google

Practice this problem

Problem Statement

There is an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. You are given a 2D integer array edges of length n - 1, where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the tree.

You are also given a 0-indexed integer array values of length n, where values[i] is the value associated with the i^th node.

You start with a score of 0. In one operation, you can:

Pick any node i.
Add values[i] to your score.
Set values[i] to 0.

A tree is healthy if the sum of values on the path from the root to any leaf node is different than zero.

Return the maximum score you can obtain after performing these operations on the tree any number of times so that it remains healthy.

Example 1:

Input: edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
Output: 11
Explanation: We can choose nodes 1, 2, 3, 4, and 5. The value of the root is non-zero. Hence, the sum of values on the path from the root to any leaf is different than zero. Therefore, the tree is healthy and the score is values[1] + values[2] + values[3] + values[4] + values[5] = 11.
It can be shown that 11 is the maximum score obtainable after any number of operations on the tree.

Example 2:

Input: edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [20,10,9,7,4,3,5]
Output: 40
Explanation: We can choose nodes 0, 2, 3, and 4.
- The sum of values on the path from 0 to 4 is equal to 10.
- The sum of values on the path from 0 to 3 is equal to 10.
- The sum of values on the path from 0 to 5 is equal to 3.
- The sum of values on the path from 0 to 6 is equal to 5.
Therefore, the tree is healthy and the score is values[0] + values[2] + values[3] + values[4] = 40.
It can be shown that 40 is the maximum score obtainable after any number of operations on the tree.

Constraints:

2 <= n <= 2 * 10⁴
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
values.length == n
1 <= values[i] <= 10⁹
The input is generated such that edges represents a valid tree.

Approach Overview

Problem Overview: You are given a tree where each node has a value. You may apply operations that collect a node’s value into the score and set that node to zero. After all operations, every root-to-leaf path must still have a non-zero total. The goal is to maximize the score collected.

Approach 1: DFS with Tree Dynamic Programming (O(n) time, O(n) space)

The key observation: instead of directly maximizing the score, compute the minimum value that must remain in the tree so every root-to-leaf path keeps a positive sum. If you know the total sum of all node values, the final score is simply totalSum - requiredSum. Use Depth-First Search to process the tree bottom‑up. For a leaf node, you must keep its value because removing it would make the path sum zero. For an internal node, you have a choice: keep the node’s value, or rely on its children to keep enough value in the subtree. Therefore the minimum required value at a node is min(nodeValue, sum(childRequired)). This recursive decision naturally forms a Dynamic Programming state on the tree. Traverse the tree, compute the required value for each subtree, and subtract the root’s required value from the total sum.

Approach 2: Iterative DFS Using Stack (O(n) time, O(n) space)

The same DP logic can be implemented iteratively to avoid recursion depth limits. Build an adjacency list and simulate post‑order traversal with a stack. Each stack frame tracks whether children have been processed. Once all children of a node are evaluated, compute its required value using the same rule: leaf nodes return their value, while internal nodes return min(nodeValue, sum(childRequired)). Store intermediate results in an array or map indexed by node. This approach is useful in environments where recursion depth may exceed limits or when you prefer explicit control over traversal.

Recommended for interviews: The recursive DFS with tree DP is the expected solution. It runs in linear time, clearly models the constraint that each path must retain value, and demonstrates comfort with tree-based dynamic programming. Mentioning the iterative DFS variant shows awareness of stack-based traversal and recursion limits.

Approach 1: DFS and Tree Traversal

Use Depth First Search (DFS) to traverse the tree and consider each node's contribution to potential scores while ensuring the tree remains healthy. The DFS approach allows us to explore all nodes by starting at the root and visiting child nodes before visiting sibling nodes, keeping track of the path value and the chosen nodes.

The solution implements DFS to explore the tree. Each node contributes its value to the current path sum. After exploring all paths from the given node, it updates the maximum score if the path sum does not become zero. This solution ensures each path from the root remains healthy by rolling back if it becomes ineffective.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2) - Due to the adjacency matrix being O(n^2) and traversing it.
Space Complexity: O(n^2) - Due to the adjacency matrix used to store the tree.

Try this approach in the editor →

Approach 2: Iterative DFS using Stack

An alternative to recursive DFS is using an iterative approach with a stack. This can help avoid recursion limitations in programming languages by simulating the call stack manually.

In this C solution, we simulate a stack to perform DFS iteratively, maintaining a running sum of path values from the root to each node. The score is checked by leaf status and non-zero sum for maximum score calculation.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2) - Adjacency matrix causes the squared factor.
Space Complexity: O(n) - Stack space used additionally.

Try this approach in the editor →

Approach 3: Tree DP

The problem is actually asking us to select some nodes from all nodes of the tree so that the sum of these nodes' values is maximized, and there is one node on each path from the root node to the leaf node that is not selected.

We can use the method of tree DP to solve this problem.

We design a function dfs(i, fa), where i represents the current node with node i as the root of the subtree, and fa represents the parent node of i. The function returns an array of length 2, where [0] represents the sum of the values of all nodes in the subtree, and [1] represents the maximum value of the subtree satisfying that there is one node not selected on each path.

The value of [0] can be obtained directly by DFS accumulating the values of each node, while the value of [1] needs to consider two situations, namely whether node i is selected. If it is selected, then each subtree of node i must satisfy that there is one node not selected on each path; if it is not selected, then all nodes of each subtree of node i can be selected. We take the maximum of these two situations.

It should be noted that the value of [1] of the leaf node is 0, because the leaf node has no subtree, so there is no need to consider the situation where there is one node not selected on each path.

The answer is dfs(0, -1)[1].

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
DFS and Tree Traversal	Time Complexity: O(n^2) - Due to the adjacency matrix being O(n^2) and traversing it. Space Complexity: O(n^2) - Due to the adjacency matrix used to store the tree.
Iterative DFS using Stack	Time Complexity: O(n^2) - Adjacency matrix causes the squared factor. Space Complexity: O(n) - Stack space used additionally.
Tree DP	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
DFS with Tree Dynamic Programming	O(n)	O(n)	Best general solution. Clean recursive logic and optimal performance.
Iterative DFS using Stack	O(n)	O(n)	Useful when recursion depth may overflow or when iterative traversal is preferred.

Video Solution

Leetcode weekly contest 370 solution | Maximum Score After Applying Operations on a Tree | Hindi • Pawan Kumar Giri • 1,885 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Score After Applying Operations on a Tree easy or hard?

The problem is typically classified as Medium difficulty. The challenge is recognizing that maximizing score is equivalent to minimizing the value that must remain in the tree. Once that insight is clear, a single DFS with tree dynamic programming solves it in linear time.

Maximum Score After Applying Operations on a Tree Python/Java solution

In Python or Java, construct the tree using an adjacency list and run a DFS that returns the required value for each subtree. Maintain the total sum of node values, compute subtree requirements with min(nodeValue, sum(childResults)), and subtract the root requirement from the total to get the maximum score.

How to solve Maximum Score After Applying Operations on a Tree in O(n)?

Build an adjacency list and run a post‑order DFS from the root. For leaf nodes, return their value since removing them would break the path constraint. For internal nodes, compute the sum of required values from children and return min(nodeValue, childSum). Track the total sum of all nodes and subtract the root’s required value to get the maximum score.

What is the best approach for Maximum Score After Applying Operations on a Tree?

The optimal approach uses DFS with tree dynamic programming. Traverse the tree bottom‑up and compute the minimum value that must remain in each subtree to keep every root‑to‑leaf path non‑zero. For each node, return min(nodeValue, sum of required values from children). The final score equals total node values minus the required value at the root. This runs in O(n) time.

Is Maximum Score After Applying Operations on a Tree asked at Google/Amazon/Meta?

Problems combining tree traversal and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require computing optimal values along root‑to‑leaf paths or subtree decisions are common in senior‑level coding interviews.

What data structure is used in Maximum Score After Applying Operations on a Tree?

The solution uses an adjacency list to represent the tree and Depth‑First Search for traversal. The algorithm also applies dynamic programming on the tree structure, where each node stores the minimum value required to preserve valid root‑to‑leaf paths.

What is the time complexity of Maximum Score After Applying Operations on a Tree?

The optimal DFS solution runs in O(n) time where n is the number of nodes in the tree. Each node and edge is visited once during traversal. Space complexity is O(n) due to the adjacency list and recursion stack (or explicit stack in the iterative version).

Ready to solve this problem?

Practice Maximum Score After Applying Operations on a Tree with our built-in code editor and test cases.

Practice on FleetCode

Collect Coins in a Tree

Find the Maximum Sum of Node Values

Problem Info

DifficultyMedium

Acceptance47.2%

Approaches3

Reading time27 min

Asked at

Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: DFS and Tree Traversal

Code

Complexity

Approach 2: Iterative DFS using Stack

Code

Complexity

Approach 3: Tree DP

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents