Given an undirected tree with N nodes numbered from 1 to N and an array A[] where A[i] denotes the value assigned to (i+1)th node. The connections between the nodes are provided in a 2-dimensional array edges[]. The task is to find the maximum path sum between any two nodes. (Both the nodes can be the same also).
Note: The path sum is equal to the sum of the value of the nodes of that path.
Examples:
Input: N = 6, A[] = {4, -1, -3, 5, 7, -2},
edges[][] = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {2, 6}}
Output: 11
Explanation: The Simple path sum between node 4 and 5 through node 2. i.e., 5-1+7 = 11
maximum path sum = 11
Input: N = 3, A[] = {2, 3, 4}, edges[][] = {{1, 2}, {1, 3}}
Output: 9
Naive Approach: A simple solution is to find the path sum between every two nodes by depth first search in the tree and then find the maximum of them.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: An efficient approach to solve the problem in one depth first search traversal is based on the following idea:
The idea is that, for each node, find two paths(the paths starting from that node and reaching to any depth) with the maximum path sum. The maximum result for that node will be equal to the sum of those two paths with the node.
The maximum among all the nodes is the maximum path sum of the tree.
Follow the steps to solve the problem:
- Use a DFS traversal starting from the root.
- Use an array to store the maximum path sum starting from a node.
- In each DFS traversal:
- Find the two maximum path sums of starting from that (say maximumBranchSum1 and maximumBranchSum2) which stores 0 if the maximum path sum is negative (because the starting and ending node of a path can be same as mentioned in the problem).
- Store the maximum path sum in the array
- The maximum path sum of the path passing through the current node and belonging to its subtree is the sum of the two maximum paths and A[i].
- The maximum value among all such maximum path sums is the required answer.
Below is the implementation for the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Final result variableint result = 0;// Helper function to calculate// the maximum path sum using DFSvoid findMaximumPathSum(int currentNode, int previousNode, vector<int> adj[], int A[]){ // Nodes to which currentNode is // connected to vector<int> v = adj[currentNode]; int maximumBranchSum1 = 0; int maximumBranchSum2 = 0; for (int i = 0; i < v.size(); i++) { // checking whether the branch is // visited already if (v[i] == previousNode) { continue; } findMaximumPathSum(v[i], currentNode, adj, A); // Storing the maximum of value of // branch path sums // maximumBranchSum1 will store the // maximum value // maximumBranchSum2 will store the // 2nd most maximum value if (A[v[i]] > maximumBranchSum1) { maximumBranchSum2 = maximumBranchSum1; maximumBranchSum1 = A[v[i]]; } else { maximumBranchSum2 = max(maximumBranchSum2, A[v[i]]); } } result = max(result, A[currentNode] + maximumBranchSum1 + maximumBranchSum2); // updating the value of current value // with maximum path sum including // currentNode A[currentNode] += maximumBranchSum1;}// Function to get the maximum path sumvoid print(int A[], int N, pair<int, int> edges[]){ vector<int> adj[N]; // adjacency list for undirected graph for (int i = 0; i < N - 1; i++) { int x = edges[i].first; int y = edges[i].second; adj[x - 1].push_back(y - 1); adj[y - 1].push_back(x - 1); } findMaximumPathSum(0, -1, adj, A); cout << result << endl;}// Driver codeint main(){ int N = 6; int A[N] = { 4, -1, -3, 5, 7, -2 }; pair<int, int> edges[N - 1] = { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 2, 5 }, { 2, 6 } }; // Function call print(A, N, edges); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to add edge static void addEdge(ArrayList<ArrayList<Integer> > adj, int s, int d) { adj.get(s).add(d); adj.get(d).add(s); } static int result = 0; // Helper function to calculate // the maximum path sum using DFS public static void findMaximumPathSum(int currentNode, int previousNode, ArrayList<ArrayList<Integer> > adj, int A[]) { // Nodes to which currentNode // is connected to ArrayList<Integer> v = adj.get(currentNode); int maximumBranchSum1 = 0, maximumBranchSum2 = 0; for (int i = 0; i < v.size(); i++) { // Checking whether the branch // is visited already if (v.get(i) == previousNode) { continue; } findMaximumPathSum(v.get(i), currentNode, adj, A); // Storing the maximum of value of branch path // sums maximumBranchSum1 will store the maximum // value maximumBranchSum2 will store the 2nd // most maximum value if (A[v.get(i)] > maximumBranchSum1) { maximumBranchSum2 = maximumBranchSum1; maximumBranchSum1 = A[v.get(i)]; } else { maximumBranchSum2 = Math.max( maximumBranchSum2, A[v.get(i)]); } } result = Math.max(result, A[currentNode] + maximumBranchSum1 + maximumBranchSum2); // Updating the value of current node with // maximum path sum including currentNode A[currentNode] += maximumBranchSum1; } // Driver code public static void main(String[] args) { int N = 6; int A[] = { 4, -1, -3, 5, 7, -2 }; ArrayList<ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer> >(N); for (int i = 0; i < N; i++) adj.add(new ArrayList<Integer>()); addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 1, 3); addEdge(adj, 1, 4); addEdge(adj, 1, 5); // Driver code findMaximumPathSum(0, -1, adj, A); System.out.println(result); }} |
Python3
# Python code to implement the approach# Function to add edgedef addEdge(adj, s, d): adj[s].append(d) adj[d].append(s)result = 0# Helper function to calculate# the maximum path sum using DFSdef findMaximumPathSum(currentNode, previousNode, adj, A): # Nodes to which currentNode # is connected to v = adj[currentNode] maximumBranchSum1 = 0 maximumBranchSum2 = 0 for i in range(len(v)): # Checking whether the branch # is visited already if (v[i] == previousNode): continue findMaximumPathSum(v[i], currentNode, adj, A) # Storing the maximum of value of branch path # sums maximumBranchSum1 will store the maximum # value maximumBranchSum2 will store the 2nd # most maximum value if (A[v[i]] > maximumBranchSum1): maximumBranchSum2 = maximumBranchSum1 maximumBranchSum1 = A[v[i]] else: maximumBranchSum2 = max(maximumBranchSum2, A[v[i]]) global result result = max(result, A[currentNode] + maximumBranchSum1 + maximumBranchSum2) # Updating the value of current node with # maximum path sum including currentNode A[currentNode] += maximumBranchSum1# Driver codeN = 6A = [4, -1, -3, 5, 7, -2]adj = []for i in range(N): adj.append([])addEdge(adj, 0, 1)addEdge(adj, 0, 2)addEdge(adj, 1, 3)addEdge(adj, 1, 4)addEdge(adj, 1, 5)# Driver codefindMaximumPathSum(0, -1, adj, A)print(result)# This code is contributed by gfgking. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;namespace MaximumPathSumInTree{ class Program { static void Main(string[] args) { int N = 6; int[] A = { 4, -1, -3, 5, 7, -2 }; List<List<int>> adj = new List<List<int>>(N); for (int i = 0; i < N; i++) adj.Add(new List<int>()); AddEdge(adj, 0, 1); AddEdge(adj, 0, 2); AddEdge(adj, 1, 3); AddEdge(adj, 1, 4); AddEdge(adj, 1, 5); // Driver code FindMaximumPathSum(0, -1, adj, A); Console.WriteLine(result); } // Function to add edge static void AddEdge(List<List<int>> adj, int s, int d) { adj[s].Add(d); adj[d].Add(s); } static int result = 0; // Helper function to calculate // the maximum path sum using DFS public static void FindMaximumPathSum(int currentNode, int previousNode, List<List<int>> adj, int[] A) { // Nodes to which currentNode // is connected to List<int> v = adj[currentNode]; int maximumBranchSum1 = 0, maximumBranchSum2 = 0; for (int i = 0; i < v.Count; i++) { // Checking whether the branch // is visited already if (v[i] == previousNode) { continue; } FindMaximumPathSum(v[i], currentNode, adj, A); // Storing the maximum of value of branch path // sums maximumBranchSum1 will store the maximum // value maximumBranchSum2 will store the 2nd // most maximum value if (A[v[i]] > maximumBranchSum1) { maximumBranchSum2 = maximumBranchSum1; maximumBranchSum1 = A[v[i]]; } else { maximumBranchSum2 = Math.Max( maximumBranchSum2, A[v[i]]); } } result = Math.Max(result, A[currentNode] + maximumBranchSum1 + maximumBranchSum2); // Updating the value of current node with // maximum path sum including currentNode A[currentNode] += maximumBranchSum1; } }}// This code is contributed by Potta Lokesh |
Javascript
<script>// Javascript code to implement the approach// Function to add edgefunction addEdge(adj, s, d) { adj[s].push(d); adj[d].push(s);}let result = 0;// Helper function to calculate// the maximum path sum using DFSfunction findMaximumPathSum(currentNode, previousNode, adj, A) { // Nodes to which currentNode // is connected to let v = adj[currentNode]; let maximumBranchSum1 = 0, maximumBranchSum2 = 0; for (let i = 0; i < v.length; i++) { // Checking whether the branch // is visited already if (v[i] == previousNode) { continue; } findMaximumPathSum(v[i], currentNode, adj, A); // Storing the maximum of value of branch path // sums maximumBranchSum1 will store the maximum // value maximumBranchSum2 will store the 2nd // most maximum value if (A[v[i]] > maximumBranchSum1) { maximumBranchSum2 = maximumBranchSum1; maximumBranchSum1 = A[v[i]]; } else { maximumBranchSum2 = Math.max( maximumBranchSum2, A[v[i]]); } } result = Math.max(result, A[currentNode] + maximumBranchSum1 + maximumBranchSum2); // Updating the value of current node with // maximum path sum including currentNode A[currentNode] += maximumBranchSum1;}// Driver codelet N = 6;let A = [4, -1, -3, 5, 7, -2];let adj = [];for (let i = 0; i < N; i++) adj.push([]);addEdge(adj, 0, 1);addEdge(adj, 0, 2);addEdge(adj, 1, 3);addEdge(adj, 1, 4);addEdge(adj, 1, 5);// Driver codefindMaximumPathSum(0, -1, adj, A);document.write(result);// This code is contributed by Saurabh Jaiswal</script> |
Output
11
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
