Maximum Path Sum
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

Question

Maximum Path Sum

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

Accepted Answer

I had to construct n-ary tree myself.
Then I used a DFS traversal starting from the root
maximum value among all maximum path sums is the required answer.

Accepted Answer

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’.

Space Complexity: O(1)Explanation:

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).

Time Complexity: O(n)Explanation:

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).

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(N)



    where 'N' is the number of nodes in the tree.

'''



from typing import List





def DFS(node, pathSum: int, maxSum: List[int]):



    # If the cuurent node is a leaf node.

    if len(node.children) == 0:



        # Update 'MAXSUM',

        maxSum[0] = max(maxSum[0], pathSum)

        return



    for child in node.children:



        # Call DFS() on the current node's children by incrementing the 'PATHSUM'.

        DFS(child, pathSum + child.data, maxSum)





def findMaxSum(n: int, root) -> int:



    # If 'ROOT' is nullptr, return 0.

    if root == None:

        return 0



    # Initialize a single element array 'MAXSUM' to store maximum path sum.

    maxSum = [0]



    DFS(root, root.data, maxSum)



    # Return 'MAXSUM'.

    return maxSum[0]

C++ (g++ 5.4)

/*
    Time Complexity : O(N)
    Space Complexity : O(N)

    where 'N' is the number of nodes in the tree.
*/

void DFS(TreeNode* node, int pathSum, int &maxSum) {
    
    // If the cuurent node is a leaf node.
    if (node->children.size() == 0) {

        // Update 'MAXSUM',
        maxSum = max(maxSum, pathSum);
        return;
    }

    for (TreeNode* child : node->children) {

        // Call DFS() on the current node's children by incrementing the 'PATHSUM'.
        DFS(child, pathSum + child->data, maxSum);
    }
}

int findMaxSum(int n, TreeNode* root)
{
    // If 'ROOT' is nullptr, return 0.
    if (root == nullptr) {

        return 0;
    }

    // Initialize a single element array 'MAXSUM' to store maximum path sum.
    int maxSum = 0;
    
    DFS(root, root->data, maxSum);

    // Return 'MAXSUM'.
    return maxSum;
}

Java (SE 1.8)

/*
    Time Complexity : O(N)
    Space Complexity : O(N)

    where 'N' is the number of nodes in the tree.
*/

public class Solution {

	public static int findMaxSum(int n, TreeNode root) {

		// If 'ROOT' is null, return 0.
		if (root == null) {

			return 0;
		}

		// Initialize a single element array 'MAXSUM' to store maximum path sum.
		int maxSum[] = {0};

		DFS(root, root.data, maxSum);

		// Return 'MAXSUM'.
		return maxSum[0];
	}

	public static void DFS(TreeNode node, int pathSum, int[] maxSum) {

		// If the cuurent node is a leaf node.
		if (node.children.size() == 0) {

			// Update 'MAXSUM'.
			maxSum[0] = Math.max(maxSum[0], pathSum);
			return;
		}

		for (TreeNode child : node.children) {

			// Call DFS() on the current node's children by incrementing the 'PATHSUM'.
			DFS(child, pathSum + child.data, maxSum);
		}
	}
}