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:
i, if amount[i] is negative, or,i, otherwise.The game goes on as follows:
0 and Bob is at node bob.0.c, then both Alice and Bob pay c / 2 each. Similarly, if the reward at the gate is c, both of them receive c / 2 each.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 != biedges represents a valid tree.1 <= bob < namount.length == namount[i] is an even integer in the range [-104, 104].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.
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.
The 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.
Python
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.
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.
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.
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.
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.
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:
t for Alice to reach node i is the same as the time ts[i] for Bob to reach node i. In this case, Alice and Bob open the door at node i at the same time, and the score Alice gets is v + \frac{amount[i]}{2}.t for Alice to reach node i is less than the time ts[i] for Bob to reach node i. In this case, Alice opens the door at node i, and the score Alice gets is v + amount[i].t for Alice to reach node i is greater than the time ts[i] for Bob to reach node i. In this case, Alice does not open the door at node i, and the score Alice gets is v, 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.
| 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 | — |
| 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 |
Most Profitable Path in a Tree - Leetcode 2467 - Python • NeetCodeIO • 14,141 views views
Watch 9 more video solutions →Practice Most Profitable Path in a Tree with our built-in code editor and test cases.
Practice on FleetCode