Most Profitable Path in a Tree
MediumUpdated: Aug 2, 2025
Practice on:
Problem
There is an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0. You are given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
At every node i, there is a gate. You are also given an array of even integers amount, where amount[i] represents:
- the price needed to open the gate at node
i, ifamount[i]is negative, or, - the cash reward obtained on opening the gate at node
i, otherwise.
The game goes on as follows:
- Initially, Alice is at node
0and Bob is at nodebob. - At every second, Alice and Bob each move to an adjacent node. Alice moves towards some leaf node, while Bob moves towards node
0. - For every node along their path, Alice and Bob either spend money to open the gate at that node, or accept the reward. Note that:
- If the gate is already open, no price will be required, nor will there be any cash reward.
- If Alice and Bob reach the node simultaneously, they share the price/reward for opening the gate there. In other words, if the price to open the gate is
c, then both Alice and Bob payc / 2each. Similarly, if the reward at the gate isc, both of them receivec / 2each.
- If Alice reaches a leaf node, she stops moving. Similarly, if Bob reaches node
0, he stops moving. Note that these events are independent of each other.
Return the maximum net income Alice can have if she travels towards the optimal leaf node._
Examples
Example 1:
graph TD 0("0<br><span style='color:blue;'>Amount: -2</span>") 1("1<br><span style='color:blue;'>Amount: 4</span>") 2("2<br><span style='color:blue;'>Amount: 2</span>") 3("3<br><span style='color:blue;'>Amount: -4</span>") 4("4<br><span style='color:blue;'>Amount: 6</span>") 0 --- 1 1 --- 2 1 --- 3 3 --- 4
Input: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
Output: 6
Explanation:
The above diagram represents the given tree. The game goes as follows:
- Alice is initially on node 0, Bob on node 3. They open the gates of their respective nodes.
Alice's net income is now -2.
- Both Alice and Bob move to node 1.
Since they reach here simultaneously, they open the gate together and share the reward.
Alice's net income becomes -2 + (4 / 2) = 0.
- Alice moves on to node 3. Since Bob already opened its gate, Alice's income remains unchanged.
Bob moves on to node 0, and stops moving.
- Alice moves on to node 4 and opens the gate there. Her net income becomes 0 + 6 = 6.
Now, neither Alice nor Bob can make any further moves, and the game ends.
It is not possible for Alice to get a higher net income.
Example 2:
graph TD 0("0<br><span style='color:blue;'>Amount: -7280</span>") 1("1<br><span style='color:blue;'>Amount: 2350</span>") 0 --- 1
Input: edges = [[0,1]], bob = 1, amount = [-7280,2350]
Output: -7280
Explanation:
Alice follows the path 0->1 whereas Bob follows the path 1->0.
Thus, Alice opens the gate at node 0 only. Hence, her net income is -7280.
Constraints:
2 <= n <= 105edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedgesrepresents a valid tree.1 <= bob < namount.length == namount[i]is an even integer in the range[-104, 104].
Solution
Method 1 - 2 DFS approach
To solve the problem of determining Alice's maximum profit while considering Bob's movement, we used a two-step Depth-First Search (DFS) approach. Here's the detailed explanation:
Step 1: Bob's Path Simulation (dfsBob)
- Goal: Calculate at what time Bob reaches each node.
- Start at node
boband recursively determine the time it takes for Bob to reach node0. - Each node along Bob's path stores the time Bob reaches it (
bobTime[node]). - If a node cannot lead to
node 0, it is removed frombobTime.
- Start at node
Step 2: Alice's Path Simulation (dfsAlice)
- Goal: Simulate Alice's journey starting from
node 0and calculate her net profit as she explores each path to a leaf node.- Traverse the tree using DFS. At each node:
- Determine whether Alice or Bob reaches the node first (compare the current time
timewithbobTime[node]). - Calculate the income for Alice at the node based on the following conditions:
- Alice reaches first: Alice collects the full
amount[node]. - Alice and Bob reach simultaneously: The
amount[node]is divided equally. - Bob reaches first: Alice receives no income or pays no fee at the node (it has already been processed by Bob).
- Alice reaches first: Alice collects the full
- Determine whether Alice or Bob reaches the node first (compare the current time
- If the current node is a leaf node (excluding the root
node 0), update the maximum income seen so far. - Continue to explore all unvisited neighbours.
- Traverse the tree using DFS. At each node:
Why Are bobTime and Alice's DFS necessary?
- The interaction between Alice and Bob at each node depends on their relative arrival times. Hence, precomputing when Bob arrives at each node (
bobTime) simplifies the calculations during Alice's traversal. - Alice's traversal ensures all paths to every leaf node are explored, guaranteeing that the optimal path is found.
Handling Special Cases
- Simultaneous Arrival: Income is divided equally between Alice and Bob.
- Bob Reaches First: The node is marked as "processed," and Alice receives no income there.
- Leaf Nodes: Only pathways ending at leaf nodes count toward maximizing Alice's net profit.
Video explanation
Here is the video explaining this method in detail. Please check it out:
<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/ckPIvAY5ZI0" frameborder="0" allowfullscreen></iframe></div>
Code
Java
class Solution {
// Represents the tree as an adjacency list
private List<List<Integer>> tree;
// Tracks when Bob reaches each node
private Map<Integer, Integer> bobTime;
// Tracks visited nodes during DFS
private boolean[] visited;
// Stores the profit or loss at each node
private int[] amount;
// Stores the maximum income Alice can achieve
private int maxIncome = Integer.MIN_VALUE;
public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
int n = amount.length;
// Initialize adjacency list for the tree
tree = new ArrayList<>();
for (int i = 0; i < n; i++) {
tree.add(new ArrayList<>());
}
// Build the tree from the provided edges
for (int[] edge : edges) {
tree.get(edge[0]).add(edge[1]); // Add edge in both directions
tree.get(edge[1]).add(edge[0]);
}
// Initialize bobTime map and visited array
bobTime = new HashMap<>();
visited = new boolean[n];
// Perform DFS to calculate Bob's arrival times
dfsBob(bob, 0);
// Store the `amount` array for Alice's traversal
this.amount = amount;
// Reset visited array for Alice's DFS
Arrays.fill(visited, false);
// Perform DFS for Alice's traversal, starting from the root (node 0)
dfsAlice(0, 0, 0);
// Return the maximum income Alice can achieve
return maxIncome;
}
// DFS to calculate when Bob reaches each node
private boolean dfsBob(int node, int time) {
bobTime.put(node, time); // Record the time Bob reaches this node
visited[node] = true; // Mark node as visited
// If Bob reaches the root, we are done
if (node == 0) {
return true;
}
// Explore neighbours recursively
for (int nei : tree.get(node)) {
if (!visited[nei]) { // Only visit unvisited nodes
if (dfsBob(nei, time + 1)) { // Recur for connected nodes
return true; // If root is reached, stop recursion
}
}
}
// If path to root doesn't exist through this node, remove it from bobTime
bobTime.remove(node);
return false;
}
// DFS to calculate Alice's maximum income
private void dfsAlice(int node, int time, int income) {
visited[node] = true; // Mark node as visited
// Update income based on Alice and Bob's arrival times
if (!bobTime.containsKey(node) || time < bobTime.get(node)) {
// If Alice reaches first or Bob never visits the node
income += amount[node];
} else if (time == bobTime.get(node)) {
// If Alice and Bob arrive simultaneously, they share the amount
income += amount[node] / 2;
}
// If Alice reaches a leaf node, update the maximum income
if (tree.get(node).size() == 1 && node != 0) { // Skip root as leaf node
maxIncome = Math.max(maxIncome, income);
}
// Recur for all unvisited neighbours
for (int nei : tree.get(node)) {
if (!visited[nei]) {
dfsAlice(nei, time + 1, income); // Recur for next node
}
}
}
}
Python
class Solution:
def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
n = len(amount) # Number of nodes
tree = [[] for _ in range(n)] # Adjacency list representation of the tree
# Build the adjacency list
for a, b in edges:
tree[a].append(b)
tree[b].append(a)
bobTime = {} # Stores the time Bob reaches each node
visited = [False] * n # Tracks visited nodes for DFS
maxIncome = float('-inf') # Stores the maximum income Alice can achieve
# Nested function for Bob's DFS
def dfsBob(node: int, time: int) -> bool:
nonlocal bobTime
bobTime[node] = time # Record Bob's arrival time
visited[node] = True # Mark node as visited
if node == 0: # If Bob reaches the root, stop
return True
for nei in tree[node]:
if not visited[nei]: # Traverse unvisited neighbours
if dfsBob(nei, time + 1):
return True
bobTime.pop(node) # Remove node if it doesn't lead to the root
return False
# Nested function for Alice's DFS
def dfsAlice(node: int, time: int, income: int):
nonlocal maxIncome
visited[node] = True # Mark node as visited
# Calculate Alice's income based on interaction with Bob
if node not in bobTime or time < bobTime[node]:
income += amount[node] # Alice reaches first
elif time == bobTime[node]:
income += amount[node] // 2 # Alice and Bob arrive simultaneously
# Update maximum income if node is a leaf
if len(tree[node]) == 1 and node != 0: # Leaf node check
maxIncome = max(maxIncome, income)
for nei in tree[node]:
if not visited[nei]: # Traverse unvisited neighbours
dfsAlice(nei, time + 1, income)
# Perform DFS for Bob starting at `bob`
dfsBob(bob, 0)
# Reset visited array for Alice's traversal
visited = [False] * n
# Perform DFS for Alice starting at the root (node 0)
dfsAlice(0, 0, 0)
return maxIncome
Complexity
- ⏰ Time complexity:
O(n)- Building the adjacency list takes
O(n)since there aren - 1edges (tree property). - A single DFS traversal is performed, which takes
O(n)time. - Another DFS traversal is performed, which also takes
O(n)time.
- Building the adjacency list takes
- 🧺 Space complexity:
O(n)- Requires
O(n)space to store all nodes and their edges. - Stores the time Bob reaches each node (
O(n)in size). - Used in both DFS traversals, requires
O(n)space. - The recursion depth in a DFS can be at most
O(n)for a skewed tree.
- Requires