Maximum sum path from the leaf to root
You are given a binary tree of 'N' nodes.

Your task is to find the path from the leaf node to the root node which has the maximum path sum among all the root to leaf paths.

For Example:

All the possible root to leaf paths are: 3, 4, -2, 4 with sum 9 5, 3, 4 with sum 12 6, 3, 4 with sum 13 Here, the maximum sum is 13. Thus, the output path will be 6, 3, 4.

Note:

There will be only 1 path with max sum.

Input format:

The very first line of input contains an integer 'T' denoting the number of queries or test cases. The first and only line of every test case contains elements of the binary tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take 0 in its place. For example, the level order input for the tree depicted in the above image would be : 4 -2 3 4 0 5 6 0 3 0 0 0 0 0 0

Explanation :

Level 1 : The root node of the tree is 4 Level 2 : Left child of 4 = -2 Right child of 4 = 3 Level 3 : Left child of -2 = 4 Right child of -2 = null (0) Left child of 3 = 5 Right child of 3 = 6 Level 4 : Left child of 4 = null (0) Right child of 4 = 3 Left child of 5 = null (0) Right child of 5 = null (0) Left child of 6 = null (0) Right child of 6 = null (0) Level 5 : Left child of 3 = null (0) Right child of 3 = null (0)

Note :

The above format was just to provide clarity on how the input is formed for a given tree. The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as: 4 -2 3 4 0 5 6 0 7 0 0 0 0 0 0

Output format:

For each test case, print integers representing the path from the leaf node to the root node which has the maximum sum separated by spaces in a single line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Maximum sum path from the leaf to root

You are given a binary tree of 'N' nodes.

Your task is to find the path from the leaf node to the root node which has the maximum path sum among all the root to leaf paths.

For Example:

sample tree

All the possible root to leaf paths are:
3, 4, -2, 4 with sum 9
5, 3, 4 with sum 12
6, 3, 4 with sum 13
Here, the maximum sum is 13. Thus, the output path will be 6, 3, 4.

Note:

There will be only 1 path with max sum.

Input format:

The very first line of input contains an integer 'T' denoting the number of queries or test cases. 

The first and only line of every test case contains elements of the binary tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take 0 in its place.

For example, the level order input for the tree depicted in the above image would be :

4
-2 3
4 0 5 6
0 3 0 0 0 0
0 0

Explanation :

Level 1 :
The root node of the tree is 4

Level 2 :
Left child of 4 = -2
Right child of 4 = 3

Level 3 :
Left child of -2 = 4
Right child of -2 = null (0)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (0)
Right child of 4 = 3
Left child of 5 = null (0)
Right child of 5 = null (0)
Left child of 6 = null (0)
Right child of 6 = null (0)

Level 5 :
Left child of 3 = null (0)
Right child of 3 = null (0)

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

4 -2 3 4 0 5 6 0 7 0 0 0 0 0 0

Output format:

For each test case, print integers representing the path from the leaf node to the root node which has the maximum sum separated by spaces in a single line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 3000
-10 ^ 5 <= DATA <= 10 ^ 5, DATA != 0

where 'T' is the number of test cases, 'N' is the number of nodes in the tree and 'DATA' is the value of each node.

Time limit: 1 sec

Accepted Answer

For each node there can be four ways that the max path goes through the node:
1. Node only
2. Max path through Left Child + Node
3. Max path through Right Child + Node
4. Max path through Left Child + Node + Max path through Right Child

The idea is to keep trace of four paths and pick up the max one in the end. An important thing to note is, root of every subtree need to return maximum path sum such that at most one child of root is involved. This is needed for parent function call. In below code, this sum is stored in ‘max_single’ and returned by the recursive function.

Accepted Answer

Recursive Subproblem

The idea here is that we will do a recursive solution by asking the children of the current node for the max sum path and then choose the path with the max sum.

The approach will be as follows:

Get the max sum path for the left subtree.
Get the max sum path for the right subtree.
Select the one with the max sum from both and insert current node's data into it.
Return the updated path.

Algorithm:

list ‘MAXPATHSUM’('ROOT'):

If the root is NULL: return empty list.
Initialize ‘LEFTPATH’ = ‘MAXPATHSUM’('ROOT'->left).
Initialize ‘LEFTPATH’ = ‘MAXPATHSUM’('ROOT'->right).
Append 'ROOT' -> data to both the lists.
Find the sum of both lists.
Return the list with the greater sum.

Space Complexity: O(n)Explanation:

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

In the worst case, we are storing at max 2 * N nodes.

Time Complexity: OtherExplanation:

O(N + H ^ 2), where ‘N’ is the number of nodes in the Binary tree and ‘H’ is the height of the binary tree.

In the worst case, for each level, we will be storing the path from the leaf node to every level and calculating the sum for the same.

Note: If the given tree is a skew tree, then time complexity will be O(N ^ 2).

Accepted Answer

Recursive

The idea here is that we will recursively get the possible maximum path sum from root to leaf, we will store this in a variable say maxSum, then, find the path with a sum equivalent to maxSum.

So the steps will be as given below:

Recursively call to get the maximum path sum for left and right subtree
Return maximum sum to be the current node’s data + max(left maximum path sum, right maximum path sum)
After getting the maximum path sum, find the path with a sum equivalent to the max path sum using recursion.

Algorithm:

int ‘GETSUM’('ROOT'):

Initialize ‘SUM’= INT_MIN
If root's left in not NULL:
- Call ‘SUM’ = max(‘SUM’, ‘GETSUM’('ROOT'→left))
If root's right is not NULL:
- Call 'SUM' = max(‘SUM’, ‘GETSUM’('ROOT'→right))
If 'SUM' == INT_MIN: update sum with 0.
Return ‘SUM’+ 'ROOT'→data;

bool ‘GETPATH’(root, &‘PATH’, &‘ANS’, sum=0):

If 'ROOT' == NULL: return true if ‘ANS’== sum, otherwise, return false.
Add root's data to sum.
Append root's data to the path.
If ‘GETPATH’('ROOT'→left, ‘PATH’, ‘ANS’, ‘SUM’) is true: return true.
If ‘GETPATH’('ROOT'→right, ‘PATH’, ‘ANS’, ‘SUM’) is true: return true.
If the path is not found yet: Delete the last element from the path
- Subtract ‘ROOT’→data from ‘SUM’
Return false

list ‘MAXSUM’('ROOT'):

Initialize ‘ANS’ = ‘GETSUM’('ROOT'), this will give you the maximum possible sum among all the root to leaf paths.
Initialize list ‘PATH’ = ‘GETPATH’('ROOT', ‘PATH’, ‘ANS’), this will give you the required path from the root to leaf.
Reverse the path and return.

Space Complexity: OtherExplanation:

O(H), where ‘H’ is the height of the Binary tree.

In the worst case, extra space is used by the recursion stack which goes to a maximum depth of ‘H’.

Time Complexity: O(n)Explanation:

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

In the worst case, we are traversing every node twice.

You are given a binary tree of 'N' nodes.

Your task is to find the path from the leaf node to the root node which has the maximum path sum among all the root to leaf paths.

For Example:

Note:

Input format:

Explanation :

Note :

Output format:

Note:

Constraints:

Top SPRINKLR Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern