Most Profitable Path in a Tree solution and explanation
Google
9 more videos on this problem
Most Profitable Path in a Tree - Leetcode 2467 - PythonNeetCodeIO · 27:17 · 14K views
Most Profitable Path in a Tree | BFS | DFS | Detailed | Leetcode 2467 | codestorywithMIKcodestorywithMIK · 44:45 · 11K views
Most Profitable Path in a Tree | Leetcode 2467Techdose · 25:59 · 5K views
2467. Most Profitable Path in a Tree | DFS | + Single DFS | TreeAryan Mittal · 32:06 · 3K views
2467. Most Profitable Path in a Tree (Leetcode Medium)Programming Live with Larry · 18:33 · 1K views
2467. Most Profitable Path in a Tree | Intuit SDE Intern OA | TreesDeep Tech · 22:15 · 1K views
2467. Most Profitable Path in a Tree || C++ solution || #leetcodeCodeQuest · 22:37 · 1K views
Leetcode 2467. Most profitable path in a tree | Microsoft interview questionCodeItUp · 18:35 · 992 views
Most Profitable Path in a Tree - Leetcode 2467 - PythonTim Huang · 8:20 · 55 views
leetcode [Daily]2467 Most Profitable Path in a Tree | recursion, trick for path direction traceCode-Yao · 15:09 · 54 views
The 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.
Example 1:
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:
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].
Approach overview
Problem Overview: You are given a tree where each node has a reward or cost. Alice starts from node 0 and moves toward any leaf, while Bob starts at a given node and moves toward the root. Each node's value is collected depending on who arrives first. The goal is to compute the maximum profit Alice can obtain along any root-to-leaf path.
Approach 1: Depth-First Search to Explore All Paths (O(n) time, O(n) space)
This approach performs a DFS from the root to explore every root-to-leaf path. First compute Bob's arrival time to each node by tracing the path from Bob's starting node to the root. Then run a DFS for Alice and compare her arrival time with Bob's. If Alice arrives earlier she collects the full amount, if both arrive simultaneously she collects half, otherwise she gets nothing. The algorithm accumulates profit along each path and tracks the maximum value seen.
Approach 2: Depth-First Search (DFS) with Path Tracking (O(n) time, O(n) space)
This version explicitly tracks the path from Bob to the root using a DFS on the tree. A map or array records Bob's arrival step for every node on that path. Then a second DFS explores Alice's possible paths while keeping track of the current depth as Alice's arrival time. The key insight is comparing arrival times at each node and adjusting the node's value before adding it to the running sum. This keeps the solution linear while avoiding repeated path computations.
Approach 3: Breadth-First Search (BFS) Approach (O(n) time, O(n) space)
This method uses breadth-first search to compute parent relationships and depths in the tree. Using those parents, you reconstruct Bob's path to the root and mark the time Bob reaches each node. After that, run a traversal (BFS or DFS) from node 0 to simulate Alice's movement through the graph. For every step compare Alice's level with Bob's recorded time and adjust the profit accordingly. BFS is useful when you want a clear level-by-level traversal and explicit distance calculations.
Recommended for interviews: The DFS with path tracking approach is the most common expectation. It cleanly separates Bob's path calculation from Alice's profit exploration and runs in linear time. Interviewers usually look for the insight of recording Bob's arrival times first, then performing a single DFS to evaluate Alice's optimal path.
Approach 1: Depth-First Search to Explore All Paths
In this approach, we use Depth-First Search (DFS) to calculate Alice's maximum possible net income. The DFS traversal allows us to visit each node, simulate Alice's and Bob's moves, and keep track of the net income Alice can achieve. We consider all possibilities for Alice moving towards a leaf and determine the most profitable path, handling cases where paths overlap with Bob.
def mostProfitablePath(edges, bob, amount):
from collections import defaultdict, deque
# Build the adjacency list for the tree
tree = defaultdict(list)
for a, b in edges:
tree[a].append(b)
tree[b].append(a)
# Arrays to keep track of the times taken to reach each node from 0 and bob
time_to_reach_alice = [-1] * len(amount)
time_to_reach_bob = [-1] * len(amount)
# BFS to calculate time to reach for Alice
def bfs_alice():
queue = deque([(0, 0)])
time_to_reach_alice[0] = 0
while queue:
current, time = queue.popleft()
for neighbor in tree[current]:
if time_to_reach_alice[neighbor] == -1:
time_to_reach_alice[neighbor] = time + 1
queue.append((neighbor, time + 1))
# BFS to calculate time to reach for Bob, stopping at 0
def bfs_bob():
queue = deque([(bob, 0)])
time_to_reach_bob[bob] = 0
while queue:
current, time = queue.popleft()
for neighbor in tree[current]:
if time_to_reach_bob[neighbor] == -1:
time_to_reach_bob[neighbor] = time + 1
queue.append((neighbor, time + 1))
bfs_alice()
bfs_bob()
# DFS to find the maximum net income
max_income = float('-inf')
def dfs(node, parent, income):
nonlocal max_income
# Calculate the net income at this node
t_a, t_b = time_to_reach_alice[node], time_to_reach_bob[node]
if t_a < t_b:
income += amount[node]
elif t_a == t_b:
income += amount[node] // 2
# Update the max_income if it's a leaf node
max_income = max(max_income, income)
for neighbor in tree[node]:
if neighbor != parent:
dfs(neighbor, node, income)
dfs(0, -1, 0)
return max_incomeThe Python solution employs a DFS approach. First, it constructs the tree using an adjacency list. Then, it uses Breadth-First Search (BFS) to calculate the time taken for both Alice and Bob to reach every node starting from their respective starting points, node 0 for Alice and `bob` for Bob. This is followed by a DFS traversal from the root, node 0, calculating the net income while considering the rules of simultaneous arrival at nodes. The global maximum income found along any path to a leaf is the answer.
Time Complexity: O(n), where n is the number of nodes. Each node is visited a constant number of times.
Space Complexity: O(n) for the adjacency list and additional storage for time calculations.
Approach 2: Depth-First Search (DFS) with Path Tracking
In this approach, we perform a DFS from node 0 to identify all possible leaf nodes along with their paths. Simultaneously, we simulate Bob's movement back to the root (node 0). During these traversals, track the income generated at each step for Alice. If Bob and Alice meet at a node, compute the shared income accordingly. This method ensures that we explore all paths to leaf nodes and account for interactions between Alice and Bob.
def most_profitable_path(edges, bob, amount):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# DFS to find all leaf paths
def dfs(node, parent, path):
if len(graph[node]) == 1 and node != 0: # Leaf node
all_paths.append(path + [node])
return
for neighbor in graph[node]:
if neighbor != parent:
dfs(neighbor, node, path + [node])
# Track paths to each leaf
all_paths = []
dfs(0, -1, [])
# Calculate all_bobs_path to root
bob_to_root = []
stack = [(bob, -1, [])]
while stack:
node, parent, path = stack.pop()
bob_to_root.append(path + [node])
for neighbor in graph[node]:
if neighbor != parent:
stack.append((neighbor, node, path + [node]))
bob_to_root = bob_to_root[-1]
leaf_profits = []
# Evaluate each path and calculate profits
for path in all_paths:
max_profit = 0
for step, node in enumerate(path):
if bob_to_root and bob_to_root[-(step + 1)] == node: # They meet at the same timestep
max_profit += amount[node] // 2
else:
max_profit += amount[node]
leaf_profits.append(max_profit)
return max(leaf_profits)import java.util.*;
public class Solution {
public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
}
List<List<Integer>> allPaths = new ArrayList<>();
dfs(0, -1, graph, new ArrayList<>(), allPaths);
List<Integer> bobPath = backtrack(bob, graph);
int maxProfit = Integer.MIN_VALUE;
for (List<Integer> path : allPaths) {
int profit = 0;
for (int i = 0; i < path.size(); i++) {
int node = path.get(i);
if (bobPath.contains(node) && bobPath.indexOf(node) == path.size() - 1 - i) {
profit += amount[node] / 2;
} else {
profit += amount[node];
}
}
maxProfit = Math.max(maxProfit, profit);
}
return maxProfit;
}
private void dfs(int node, int parent, Map<Integer, List<Integer>> graph, List<Integer> path, List<List<Integer>> allPaths) {
path.add(node);
boolean isLeaf = true;
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (neighbor != parent) {
isLeaf = false;
dfs(neighbor, node, graph, path, allPaths);
}
}
if (isLeaf && node != 0) {
allPaths.add(new ArrayList<>(path));
}
path.remove(path.size() - 1);
}
private List<Integer> backtrack(int bob, Map<Integer, List<Integer>> graph) {
List<Integer> path = new ArrayList<>();
dfsBob(bob, -1, graph, new ArrayList<>(), path);
return path;
}
private boolean dfsBob(int node, int parent, Map<Integer, List<Integer>> graph, List<Integer> path, List<Integer> bobPath) {
path.add(node);
if (node == 0) {
bobPath.addAll(path);
return true;
}
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (neighbor != parent) {
if (dfsBob(neighbor, node, graph, path, bobPath)) {
return true;
}
}
}
path.remove(path.size() - 1);
return false;
}
}This Python code initializes a graph from the given edges using an adjacency list representation. A DFS function identifies all paths from the root node (0) to each leaf node. These paths represent possible routes Alice can take.
The bob_to_root path is a list that contains the step-by-step path Bob takes to reach the root node from his starting position.
For each leaf path, calculate possible profits accounting for any node encounters with Bob. If Alice and Bob arrive at a node simultaneously, they share the reward/price by halving it. Finally, the highest profit across all paths is returned.
Time Complexity: O(n), where n is the number of nodes, due to examining each node in DFS.
Space Complexity: O(n), due to storing paths and other data.
Approach 3: Breadth-First Search (BFS) Approach
Instead of using DFS, we can perform a BFS to simultaneously explore levels of nodes from the starting points of Alice and Bob. This allows us to effectively monitor when they reach each node, and thus compute the shared income where necessary.
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
unordered_map<int, vector<int>> graph;
for (auto& e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
// BFSt to determine levels (distances)
vector<int> level(amount.size(), -1);
queue<int> q;
q.push(0);
level[0] = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : graph[node]) {
if (level[neighbor] == -1) {
level[neighbor] = level[node] + 1;
q.push(neighbor);
}
}
}
// BFS for Bob to reach the root
vector<int> bobLevel(amount.size(), -1);
q.push(bob);
bobLevel[bob] = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : graph[node]) {
if (bobLevel[neighbor] == -1) {
bobLevel[neighbor] = bobLevel[node] + 1;
q.push(neighbor);
}
}
}
// Calculate the most profitable path
int maxProfit = INT_MIN;
for (int i = 0; i < amount.size(); ++i) {
int aliceAmount = amount[i];
if (level[i] == bobLevel[i]) {
aliceAmount /= 2;
}
maxProfit = max(maxProfit, aliceAmount);
}
return maxProfit;
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 100000
typedef struct {
int to;
int next;
} Edge;
Edge edges[MAXN * 2];
int head[MAXN], edgeCnt;
void addEdge(int u, int v) {
edges[edgeCnt].to = v;
edges[edgeCnt].next = head[u];
head[u] = edgeCnt++;
}
void bfs(int* level, int start, int n) {
bool visited[n];
for (int i = 0; i < n; ++i) visited[i] = false;
int queue[n], front = 0, rear = 0;
queue[rear++] = start;
visited[start] = true;
level[start] = 0;
while (front < rear) {
int node = queue[front++];
for (int i = head[node]; i != -1; i = edges[i].next) {
int neighbor = edges[i].to;
if (!visited[neighbor]) {
level[neighbor] = level[node] + 1;
queue[rear++] = neighbor;
visited[neighbor] = true;
}
}
}
}
int mostProfitablePath(int n, int edgesArr[][2], int edgesSize, int bob, int* amount) {
for (int i = 0; i < n; ++i) head[i] = -1;
edgeCnt = 0;
for (int i = 0; i < edgesSize; ++i) {
addEdge(edgesArr[i][0], edgesArr[i][1]);
addEdge(edgesArr[i][1], edgesArr[i][0]);
}
int levelAlice[n], levelBob[n];
bfs(levelAlice, 0, n);
bfs(levelBob, bob, n);
int maxProfit = -999999;
for (int i = 0; i < n; ++i) {
int gain = amount[i];
if (levelAlice[i] == levelBob[i]) {
gain /= 2;
}
if (gain > maxProfit) {
maxProfit = gain;
}
}
return maxProfit;
}This C++ solution uses BFS to calculate the 'level' of each node, meaning the shortest path distance from the root (node 0) to each node in the tree. Another BFS tracks Bob's position back to 0. For each node, we compare the distance from Alice to Bob and halve the reward if both reach the node simultaneously.
Time Complexity: O(n) due to performing BFS twice for each node.
Space Complexity: O(n) due to storing the level information and graph adjacency list.
Approach 4: Two DFS Traversals
According to the problem, we know that Bob's moving path is fixed, that is, starting from node bob and finally reaching node 0. Therefore, we can first run a DFS to find out the time it takes for Bob to reach each node, which we record in the array ts.
Then we run another DFS to find the maximum score for each of Alice's moving paths. We denote the time for Alice to reach node i as t, and the current cumulative score as v. After Alice passes node i, the cumulative score has three cases:
- The time
tfor Alice to reach nodeiis the same as the timets[i]for Bob to reach nodei. In this case, Alice and Bob open the door at nodeiat the same time, and the score Alice gets isv + \frac{amount[i]}{2}. - The time
tfor Alice to reach nodeiis less than the timets[i]for Bob to reach nodei. In this case, Alice opens the door at nodei, and the score Alice gets isv + amount[i]. - The time
tfor Alice to reach nodeiis greater than the timets[i]for Bob to reach nodei. In this case, Alice does not open the door at nodei, and the score Alice gets isv, which remains unchanged.
When Alice reaches a leaf node, update the maximum score.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
func mostProfitablePath(edges [][]int, bob int, amount []int) int {
n := len(edges) + 1
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
ts := make([]int, n)
for i := range ts {
ts[i] = n
}
var dfs1 func(int, int, int) bool
dfs1 = func(i, fa, t int) bool {
if i == 0 {
ts[i] = min(ts[i], t)
return true
}
for _, j := range g[i] {
if j != fa && dfs1(j, i, t+1) {
ts[j] = min(ts[j], t+1)
return true
}
}
return false
}
dfs1(bob, -1, 0)
ts[bob] = 0
ans := -0x3f3f3f3f
var dfs2 func(int, int, int, int)
dfs2 = func(i, fa, t, v int) {
if t == ts[i] {
v += amount[i] >> 1
} else if t < ts[i] {
v += amount[i]
}
if len(g[i]) == 1 && g[i][0] == fa {
ans = max(ans, v)
return
}
for _, j := range g[i] {
if j != fa {
dfs2(j, i, t+1, v)
}
}
}
dfs2(0, -1, 0, 0)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search to Explore All Paths | Time Complexity: O(n), where n is the number of nodes. Each node is visited a constant number of times. |
| Depth-First Search (DFS) with Path Tracking | Time Complexity: O(n), where n is the number of nodes, due to examining each node in DFS. |
| Breadth-First Search (BFS) Approach | Time Complexity: O(n) due to performing BFS twice for each node. |
| Two DFS Traversals | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS to Explore All Paths | O(n) | O(n) | Good for understanding the problem by exploring every root-to-leaf path |
| DFS with Path Tracking | O(n) | O(n) | Best interview solution; separates Bob timing calculation and Alice traversal |
| BFS Approach | O(n) | O(n) | Useful when computing levels, parent arrays, or explicit shortest paths |
Frequently asked questions
Is Most Profitable Path in a Tree easy or hard?
The problem is rated Medium because the traversal itself is straightforward but the timing interaction between Alice and Bob adds a tricky constraint. Recognizing that Bob's path can be precomputed and stored simplifies the logic and keeps the algorithm linear.
Most Profitable Path in a Tree Python/Java solution
Python and Java solutions typically use adjacency lists and recursive DFS. The first DFS records Bob's arrival time for nodes on the path to the root. The second DFS evaluates Alice's profit along every path and returns the maximum. Both implementations run in O(n) time.
How to solve Most Profitable Path in a Tree in O(n)?
Build an adjacency list for the tree, then compute Bob's arrival time to nodes along his path to the root. After that, run a DFS from node 0 while tracking Alice's step count. At each node compare Alice's time with Bob's stored time to decide whether she collects the full value, half, or none. Keep the maximum profit across all root-to-leaf paths.
What is the best approach for Most Profitable Path in a Tree?
The most effective approach uses two DFS passes. First compute the time Bob reaches each node by tracing the path from Bob's starting node to the root. Then perform a DFS from node 0 for Alice, comparing arrival times to determine whether she gets full, half, or zero value from each node. This runs in O(n) time and O(n) space.
Is Most Profitable Path in a Tree asked at Google/Amazon/Meta?
Tree and graph traversal problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The problem tests DFS/BFS knowledge, path tracking, and reasoning about arrival times in graphs, which are common interview themes.
What data structure is used in Most Profitable Path in a Tree?
The core data structure is an adjacency list representing the tree as a graph. Depth-first search or breadth-first search traversals are used to compute parent relationships, node depths, and Bob's arrival times. Arrays or hash maps store timing information for comparison during Alice's traversal.
What is the time complexity of Most Profitable Path in a Tree?
The optimal solutions run in O(n) time where n is the number of nodes in the tree. Each node and edge is processed a constant number of times during the DFS or BFS traversals. Space complexity is also O(n) due to adjacency lists, recursion stack, and arrays storing Bob's arrival times.