Last Updated: 12 Dec, 2021

Longest Path

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now