Last Updated: 21 Nov, 2021
Maximum Path Sum
Easy
Asked in companies
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.
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
Approaches
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’.