Given a generic tree consisting of N nodes, the task is to find the maximum sum of the path from the root to the leaf node.
Examples:
Input:
Output: 12
Explanation: The path sum to every leaf from the root are:
For node 4: 1 -> 2 -> 4 = 7
For node 5: 1 -> 2 -> 5 = 8
For node 6: 1 -> 3 -> 6 = 10
For node 7: 1 -> 3 -> 7 = 11
For node 8: 1 -> 3 -> 8 = 12 (maximum)The maximum path sum is 12 i.e., from root 1 to leaf 8.
Approach: The given problem can be solved by performing the DFS traversal on the given tree. The idea is to perform the DFS Traversal from the root node of the given generic tree by keeping the track of the sum of values of nodes in each path and if any leaf node occurs then maximize the value of the current sum of path obtained in a variable, say maxSum.
After performing the DFS Traversal, print the value of maxSum as the resultant maximum sum path.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure of a node in the treestruct Node { int val; vector<Node*> child;};// Utility function to create a// new node in the treeNode* newNode(int key){ Node* temp = new Node; temp->val = key; return temp;}// Recursive function to calculate the// maximum sum in a path using DFSvoid DFS(Node* root, int sum, int& ans){ // If current node is a leaf node if (root->child.size() == 0) { ans = max(ans, sum); return; } // Traversing all children of // the current node for (int i = 0; i < root->child.size(); i++) { // Recursive call for all // the children nodes DFS(root->child[i], sum + root->child[i]->val, ans); }}// Driver Codeint main(){ // Given Generic Tree Node* root = newNode(1); (root->child).push_back(newNode(2)); (root->child).push_back(newNode(3)); (root->child[0]->child).push_back(newNode(4)); (root->child[1]->child).push_back(newNode(6)); (root->child[0]->child).push_back(newNode(5)); (root->child[1])->child.push_back(newNode(7)); (root->child[1]->child).push_back(newNode(8)); // Stores the maximum sum of a path int maxSumPath = 0; // Function Call DFS(root, root->val, maxSumPath); cout << maxSumPath; return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main{ // Stores the maximum sum of a path static int maxSumPath = 0; // Structure of a node in the tree static class Node { public int val; public Vector<Node> child; public Node(int key) { val = key; child = new Vector<Node>(); } } // Utility function to create a // new node in the tree static Node newNode(int key) { Node temp = new Node(key); return temp; } // Recursive function to calculate the // maximum sum in a path using DFS static void DFS(Node root, int sum) { // If current node is a leaf node if (root.child.size() == 0) { maxSumPath = Math.max(maxSumPath, sum); return; } // Traversing all children of // the current node for (int i = 0; i < root.child.size(); i++) { // Recursive call for all // the children nodes DFS(root.child.get(i), sum + root.child.get(i).val); } } public static void main(String[] args) { // Given Generic Tree Node root = newNode(1); (root.child).add(newNode(2)); (root.child).add(newNode(3)); (root.child.get(0).child).add(newNode(4)); (root.child.get(1).child).add(newNode(6)); (root.child.get(0).child).add(newNode(5)); (root.child.get(1)).child.add(newNode(7)); (root.child.get(1).child).add(newNode(8)); // Function Call DFS(root, root.val); System.out.print(maxSumPath); }}// This code is contributed by divyeshrabadiya07. |
Python3
# Python3 program for the above approach# Stores the maximum sum of a pathmaxSumPath = 0# Structure of a node in the treeclass Node: def __init__(self, key): self.val = key self.child = []# Utility function to create a# new node in the treedef newNode(key): temp = Node(key) return temp# Recursive function to calculate the# maximum sum in a path using DFSdef DFS(root, Sum): global maxSumPath # If current node is a leaf node if (len(root.child) == 0): maxSumPath = max(maxSumPath, Sum) return # Traversing all children of # the current node for i in range(len(root.child)): # Recursive call for all # the children nodes DFS(root.child[i], Sum + root.child[i].val)# Given Generic Treeroot = newNode(1)(root.child).append(newNode(2))(root.child).append(newNode(3))(root.child[0].child).append(newNode(4))(root.child[1].child).append(newNode(6))(root.child[0].child).append(newNode(5))(root.child[1]).child.append(newNode(7))(root.child[1].child).append(newNode(8))# Function CallDFS(root, root.val)print(maxSumPath)# This code is contributed by rameshtravel07. |
C#
// C# program for the above approachusing System;using System.Collections;using System.Collections.Generic;class GFG { // Stores the maximum sum of a path static int maxSumPath = 0; // Structure of a node in the tree class Node { public int val; public List<Node> child; public Node(int key) { val = key; child = new List<Node>(); } } // Utility function to create a // new node in the tree static Node newNode(int key) { Node temp = new Node(key); return temp; } // Recursive function to calculate the // maximum sum in a path using DFS static void DFS(Node root, int sum) { // If current node is a leaf node if (root.child.Count == 0) { maxSumPath = Math.Max(maxSumPath, sum); return; } // Traversing all children of // the current node for (int i = 0; i < root.child.Count; i++) { // Recursive call for all // the children nodes DFS(root.child[i], sum + root.child[i].val); } } static void Main() { // Given Generic Tree Node root = newNode(1); (root.child).Add(newNode(2)); (root.child).Add(newNode(3)); (root.child[0].child).Add(newNode(4)); (root.child[1].child).Add(newNode(6)); (root.child[0].child).Add(newNode(5)); (root.child[1]).child.Add(newNode(7)); (root.child[1].child).Add(newNode(8)); // Function Call DFS(root, root.val); Console.Write(maxSumPath); }}// This code is contributed by mukesh07. |
Javascript
<script> // Javascript program for the above approach // Stores the maximum sum of a path let maxSumPath = 0; // Structure of a node in the tree class Node { constructor(key) { this.child = []; this.val = key; } } // Utility function to create a // new node in the tree function newNode(key) { let temp = new Node(key); return temp; } // Recursive function to calculate the // maximum sum in a path using DFS function DFS(root, sum) { // If current node is a leaf node if (root.child.length == 0) { maxSumPath = Math.max(maxSumPath, sum); return; } // Traversing all children of // the current node for (let i = 0; i < root.child.length; i++) { // Recursive call for all // the children nodes DFS(root.child[i], sum + root.child[i].val); } } // Given Generic Tree let root = newNode(1); (root.child).push(newNode(2)); (root.child).push(newNode(3)); (root.child[0].child).push(newNode(4)); (root.child[1].child).push(newNode(6)); (root.child[0].child).push(newNode(5)); (root.child[1]).child.push(newNode(7)); (root.child[1].child).push(newNode(8)); // Function Call DFS(root, root.val); document.write(maxSumPath); // This code is contributed by decode2207.</script> |
Output:
12
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
