Most Profitable Path in a Tree - Practice Coding Problems

Most Profitable Path in a Tree - 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, 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.

Input & Output

Example 1 — Basic Tree Structure

$ Input: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]

› Output: 6

💡 Note: Alice path: 0→1→3→4. At node 0: Alice gets -2. At node 1: Alice gets 4. At node 3: Bob starts here at t=0, Alice arrives at t=2, so Alice gets full -4. At node 4: Alice gets 6. Total: -2+4+(-4)+6 = 4. But Alice can also go 0→1→2 for total -2+4+2 = 4. Actually, the optimal is when Alice goes to leaf 4, getting total income 6.

Example 2 — Sharing Scenario

$ Input: edges = [[0,1]], bob = 1, amount = [-7280,2350]

› Output: -2465

💡 Note: Alice goes 0→1. At node 0: Alice gets -7280. At node 1: Bob starts here, Alice arrives at t=1, Bob reaches root at t=1, but Bob is moving toward node 0, so they don't meet. Alice gets full 2350. Total: -7280+2350 = -4930. Actually, they meet at different times so Alice gets the amounts based on timing.

Example 3 — Multiple Paths

$ Input: edges = [[0,1],[0,2]], bob = 2, amount = [100,-200,300]

› Output: 400

💡 Note: Alice can go 0→1 (total 100+(-200)=-100) or 0→2. If Alice goes 0→2: At node 0, Alice gets 100. At node 2, Bob starts here but Alice arrives at t=1, and Bob moves toward 0, so timing determines sharing. Alice path 0→2 gives better income.

Constraints

1 ≤ n ≤ 10⁵
edges.length == n - 1
0 ≤ ai, bi < n
ai ≠ bi
edges represents a valid tree
1 ≤ bob < n
amount.length == n
-10⁴ ≤ amount[i] ≤ 10⁴
amount[i] is even

Visualization

Tap to expand

Understanding the Visualization

Setup

Alice starts at root 0, Bob starts at given position

Movement

Both move simultaneously - Alice to leaves, Bob to root

Rewards

Share rewards when meeting, full reward otherwise

Key Takeaway

🎯 Key Insight: Pre-calculate Bob's movement timeline to enable efficient path optimization for Alice

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to pre-compute Bob's path timing using BFS, then use DFS to explore Alice's paths with O(1) conflict resolution. The optimal approach runs in O(n) time by avoiding redundant path calculations. Best approach: Optimized DFS with pre-computed Bob timeline. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS with Pre-computed Bob Path	O(n)	O(n)	Pre-calculate Bob's movement timeline for efficient conflict resolution
Brute Force DFS	O(n²)	O(n)	Try all possible paths for Alice and simulate Bob's movement

Optimized DFS with Pre-computed Bob Path — Algorithm Steps

Step 1: Use BFS to find Bob's path to root
Step 2: Store Bob's arrival time at each node
Step 3: DFS from Alice's start with efficient conflict resolution
Step 4: Return maximum income from all leaf paths

Visualization

Tap to expand

Step-by-Step Walkthrough

BFS Bob's Path

Find Bob's path to root with timing

Store Timing

Map each node to Bob's arrival time

DFS Alice Paths

Explore paths with O(1) conflict check

Optimal Income

Return maximum across all paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 10000

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
int bobTime[MAX_N];
int hasBobTime[MAX_N];
int amount[MAX_N];
int n;
int maxIncome;

void dfs(int node, int parent, int aliceTime, int income) {
    int currentIncome = income;
    if (hasBobTime[node] && bobTime[node] == aliceTime) {
        currentIncome += amount[node] / 2;
    } else if (!hasBobTime[node] || bobTime[node] > aliceTime) {
        currentIncome += amount[node];
    }
    
    int children[MAX_N];
    int childCount = 0;
    for (int i = 0; i < graphSize[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != parent) {
            children[childCount++] = neighbor;
        }
    }
    
    if (childCount == 0) {
        if (currentIncome > maxIncome) {
            maxIncome = currentIncome;
        }
    } else {
        for (int i = 0; i < childCount; i++) {
            dfs(children[i], node, aliceTime + 1, currentIncome);
        }
    }
}

int solution(int edges[][2], int edgeCount, int bob, int* amt, int amtSize) {
    n = amtSize;
    maxIncome = INT_MIN;
    
    memset(graphSize, 0, sizeof(graphSize));
    memset(hasBobTime, 0, sizeof(hasBobTime));
    
    for (int i = 0; i < amtSize; i++) {
        amount[i] = amt[i];
    }
    
    for (int i = 0; i < edgeCount; i++) {
        int a = edges[i][0], b = edges[i][1];
        graph[a][graphSize[a]++] = b;
        graph[b][graphSize[b]++] = a;
    }
    
    // Find Bob's path using BFS
    int queue[MAX_N][2];
    int visited[MAX_N] = {0};
    int front = 0, rear = 0;
    
    queue[rear][0] = bob;
    queue[rear][1] = 0;
    rear++;
    visited[bob] = 1;
    
    while (front < rear) {
        int node = queue[front][0];
        int time = queue[front][1];
        front++;
        
        bobTime[node] = time;
        hasBobTime[node] = 1;
        
        if (node == 0) break;
        
        for (int i = 0; i < graphSize[node]; i++) {
            int neighbor = graph[node][i];
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                queue[rear][0] = neighbor;
                queue[rear][1] = time + 1;
                rear++;
            }
        }
    }
    
    dfs(0, -1, 0, 0);
    return maxIncome;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int edges[MAX_N][2];
    int edgeCount = 0;
    
    char* ptr = line + 1;
    while (*ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgeCount][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            edges[edgeCount][1] = atoi(ptr);
            edgeCount++;
            while (*ptr != ']') ptr++;
            ptr++;
        } else {
            ptr++;
        }
    }
    
    int bob;
    scanf("%d", &bob);
    
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int amount[MAX_N];
    int amtSize = 0;
    ptr = line + 1;
    while (*ptr != ']') {
        if (*ptr >= '-' || (*ptr >= '0' && *ptr <= '9')) {
            amount[amtSize++] = atoi(ptr);
            if (*ptr == '-') ptr++;
            while (*ptr >= '0' && *ptr <= '9') ptr++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(edges, edgeCount, bob, amount, amtSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single BFS for Bob's path plus DFS traversal of tree

✓ Linear Growth

Space Complexity

O(n)

Hash map for Bob's timing and recursion stack

⚡ Linearithmic Space

15.4K Views

Medium Frequency

~25 min Avg. Time

487 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS with Pre-computed Bob Path — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler