Longest Path

Easy

0/40

Average time to solve is 10m

Contributed by

6 upvotes

Asked in companies

Problem statement

You are given a series of rooms, with each room having a path to at most two other rooms. In short, they are represented as a Binary tree.

Each room has some amount of money. You can start from the root and only go downwards. Find the amount of money you can earn on the longest path. If there are multiple longest paths, find the one where you can earn maximum money.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains 'T', denoting the number of test cases.
For each Test :
The first line contains one integer, Num.
The second line contains an array A of Num space separated integers, with a positive integer representing a node and -1 representing  a NULL value. The input is given in 'Level Order'. See samples explanation for more detail.
( Note that Num is not the number of nodes, and number of nodes = number of positive integers in A.)

Output Format:

For each test case, print one integer, that is, the total money you can earn from the longest path.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints -

1 <= T <= 10
1 <= Num <= 10^5
1 <= A[i] <= 10^4 or A[i] = -1, i ∈ (1,Num)

Note - The sum of 'Num’ over all test cases does not exceed 10^5.

Time Limit: 1 sec

Sample Input 1:

1
11
4 100 2 -1 -1 5 9 -1 -1 -1 -1

Sample Output 1

Explanation for Sample Input 1:

There are two paths on length 3 here, namely 4->2->9 and 4->2->5. Out of these two, 4 -> 2 -> 9 has the greater sum, so the answer is 4+2+9=15.

Sample Input 2:

1
13
7 2 9 1 5 -1 14 -1 -1 -1 -1 -1 -1

Sample Output 2:

Hint 1

Can we recursively compute the sum of the longest path from starting at any node?

Approaches (1)

Approach 1

Recursive Solution

Approach: For each node, we can recursively compute the sum of the longest path starting at that node, using the already computed values of its children.

We can store a pair of values, denoting the maximum length from that path, and its sum. If there are multiple paths of the same length, we choose the one with the maximum sum.

Algorithm:

At each node, recursively do the following
- If the node is null, return.
- Recur for the left subtree
- Recur for the right subtree
- Out of the left and right subtree, pick the longer path.
- Adding 1 to the longer path, gives the longest path from the current node.
- Adding the value of the current node to the max sum gives the current sum.
The max sum value stored at the root is the answer.

Time Complexity

O(N), where N is the number of nodes in the Binary tree.

Since we compute the value at each node only once using the values of its left and right children, it is linear. Hence, the overall complexity is O(N).

Space Complexity

O(1), as we use only constant space.

(100% EXP penalty)

Longest Path

Console