Skip to main content
Talentd

Most Profitable Path in a Tree - Solution & Explanation

MediumArrayTreeDepth-First SearchBreadth-First Search21 min readAsked at: Amazon, Meta, Uber +3
Practice this problem

Problem Statement

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, if amount[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 0 and Bob is at node bob.
  • 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 pay c / 2 each. Similarly, if the reward at the gate is c, both of them receive c / 2 each.
  • 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 <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges represents a valid tree.
  • 1 <= bob < n
  • amount.length == n
  • amount[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.

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

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.

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.

Code

C++C

C++

C

Complexity

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.

Try this approach in the editor →

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:

  1. The time 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}.
  2. The time 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].
  3. The time 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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) for the adjacency list and additional storage for time calculations.

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.
Space Complexity: O(n), due to storing paths and other data.

Breadth-First Search (BFS) Approach

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.

Two DFS Traversals—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS to Explore All PathsO(n)O(n)Good for understanding the problem by exploring every root-to-leaf path
DFS with Path TrackingO(n)O(n)Best interview solution; separates Bob timing calculation and Alice traversal
BFS ApproachO(n)O(n)Useful when computing levels, parent arrays, or explicit shortest paths

Video Solution

Most Profitable Path in a Tree - Leetcode 2467 - Python • NeetCodeIO • 14,448 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Most Profitable Path in a Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Snakes and Ladders

Next

Time Taken to Mark All Nodes