Most Profitable Path in a Tree

Most Profitable Path in a Tree

What is this problem about?

The Most Profitable Path in a Tree presents a tree where Bob travels from a specific node toward the root, and Alice travels from the root toward a leaf. Both move simultaneously and collect gate rewards along their paths. When they're at the same node simultaneously, they split the reward. Alice wants to maximize her total collected reward. This Most Profitable Path in a Tree coding problem requires tracking Bob's path timing with DFS.

Why is this asked in interviews?

Uber, Meta, Intuit, Amazon, and Google ask this because it requires combining two DFS passes: one to find Bob's path from his node to the root (with timing), and another to simulate Alice's journey and compute optimal rewards. The array, BFS, graph, DFS, and tree interview pattern is fully exercised, and the timing coordination between two simultaneous traversals tests structured thinking.

Algorithmic pattern used

Two-pass DFS. Pass 1: Find Bob's path from his start node to the root — record the time step at which Bob reaches each node on his path. Pass 2: DFS from root, simulating Alice's journey. For each node Alice visits, compute the reward: full reward if Bob hasn't reached it yet, half if Bob arrives simultaneously, or 0 if Bob arrived first. Track the maximum total reward at any leaf.

Example explanation

Tree rooted at 0. Bob starts at node 3, path: 3→1→0. Bob's times: {3:0, 1:1, 0:2}. Gate rewards: [−2,4,2,−4]. Alice at root (time=0): reward at 0 = split if Bob arrives at time 2 (Alice at step 0 < 2 → full reward = −2? or 0 if negative). Alice moves to node 1 (time=1): Bob also at 1 at time 1 → split. Reward = 4/2=2. Alice at leaf: compute best path total.

Common mistakes candidates make

• Not precomputing Bob's path before running Alice's DFS.
• Incorrect timing comparison (< vs ≤ for simultaneous arrival).
• Not exploring all leaf paths for Alice (DFS must reach all leaves).
• Forgetting that negative rewards can be avoided by not visiting certain paths.

Interview preparation tip

Two-agent tree problems require first establishing the deterministic agent's timeline (Bob's path is fixed), then optimizing the non-deterministic agent (Alice's path) against it. Always separate these two phases. Bob's path can be found with a single DFS from his node to root. Alice's optimal path uses a DFS from root tracking cumulative rewards. Practice problems involving two simultaneous actors on trees — they appear in competitive programming and senior interviews at top tech companies.