Maximum Path Sum

Easy
0/40
profile
Contributed by
1 upvote
Asked in companies
Goldman SachsMicrosoftOracle

Problem statement

You are given an n-ary tree consisting of ‘N’ nodes. Your task is to return the maximum sum of the path from the root to the leaf node.

For example: 
For the given tree:


The path 1 -> 3 -> 7 produces the maximum i.e, 11.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integer 'N', which denotes the number of nodes in the tree.

The second line of each test case contains elements of the N-ary tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is changed, we take -1. The first not-null node(of the previous level) is treated as the parent of the first node of the current level. The second not-null node (of the previous level) is treated as the parent node for the next nodes of the current level and so on.
Output Format: 
For each test case, print the maximum sum of the path from the root to the leaf node.

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything, it has already been taken care of.
Constraints: 
1 <= T <= 10
1 <= N <= 5000
0 <= DATA <= 10^4

Where ‘T’ is the number of test cases, and ‘N’ is the total number of nodes in the binary tree, and “DATA” is the value of the tree node.

Time Limit: 1 sec
Sample Input 1:
2
7
1 2 3 -1 4 5 6 -1 7 -1 -1 -1 -1 -1
4
1 2 3 4 -1 -1 -1 -1
Sample Output 1:
11
5
Explanation of Sample Input 1:
Test Case 1: Given the tree:


The path (1 -> 3 -> 7) produces the maximum sum i.e, 11.

Test Case 2: Given the tree:


The path (1 -> 5) produces the maximum sum i.e, 5.
Sample Input 2:
2 
3
1 3 -1 5 -1 -1
5
10 9 8 -1 1 2 -1 -1 -1 -1
Sample Output 2:
9
21
Hint

Check the sum of every path from the root to the leaf node.

Approaches (1)
Depth-First Search

Prerequisite: Depth-First Search.

 

In this approach, we will use DFS. We will perform DFS from the root node of the given tree. We will use a global variable ‘MAXSUM’ to store maximum path sum and a variable ‘PATHSUM’ to keep track of each path sum, and whenever we reach any leaf node, we will update the ‘MAXSUM’ if the current path is greater than ‘MAXSUM’. The final value of ‘MAXSUM’ after the DFS is completed will be our answer.

 

Algorithm :

  • If 'ROOT' is null, return 0.
  • Initialize a variable ‘MAXSUM’ to store the maximum path sum.
  • Call DFS(‘ROOT’, ‘ROOT.DATA’, ‘MAXSUM’).
  • Return ‘MAXSUM’.

 

Maintain a function ‘DFS’(TreeNode ’NODE’, int ‘PATHSUM’, int ‘MAXSUM’).

  • If the current node is a leaf node:
    • Set ‘MAXSUM’ as the maximum of ‘MAXSUM’ and ‘PATHSUM’.
    • Return.
  • Call DFS() on the current node's children by incrementing the 'PATHSUM' by the current child’s data.

Note: We will be using single-element array ‘MAXSUM[0]’ instead of an integer variable ‘MAXSUM’ in java because we can only pass an object by reference in java and not a primitive type like ‘INT’.

Time Complexity

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

While traversing, we visit each node of the given tree which takes O(N) times. Hence the total time complexity is O(N).

Space Complexity

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

 

The maximum internal stack size will be equal to the height of the tree which is N in the worst case(when a skewed tree is given). Hence, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Maximum Path Sum
Full screen
Console