Given a binary tree containing n nodes. The problem is to find the sum of all nodes on the longest path from root to leaf node. If two or more paths compete for the longest path, then the path having maximum sum of nodes is being considered.
Examples:
Input : Binary tree:
4
/
2 5
/ /
7 1 2 3
/
6
Output : 13
4
/
2 5
/ /
7 1 2 3
/
6
The highlighted nodes (4, 2, 1, 6) above are
part of the longest root to leaf path having
sum = (4 + 2 + 1 + 6) = 13
Approach: Recursively find the length and sum of nodes of each root to leaf path and accordingly update the maximum sum.
Algorithm:
sumOfLongRootToLeafPath(root, sum, len, maxLen, maxSum)
if root == NULL
if maxLen < len
maxLen = len
maxSum = sum
else if maxLen == len && maxSum is less than sum
maxSum = sum
return
sumOfLongRootToLeafPath(root-left, sum + root-data,
len + 1, maxLen, maxSum)
sumOfLongRootToLeafPath(root-right, sum + root-data,
len + 1, maxLen, maxSum)
sumOfLongRootToLeafPathUtil(root)
if (root == NULL)
return 0
Declare maxSum = Minimum Integer
Declare maxLen = 0
sumOfLongRootToLeafPath(root, 0, 0, maxLen, maxSum)
return maxSum
C++
// C++ implementation to find the sum of nodes // on the longest path from root to leaf node #include <bits/stdc++.h> using namespace std; // Node of a binary tree struct Node { int data; Node* left, *right; }; // function to get a new node Node* getNode(int data) { // allocate memory for the node Node* newNode = (Node*)malloc(sizeof(Node)); // put in the data newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // function to find the sum of nodes on the // longest path from root to leaf node void sumOfLongRootToLeafPath(Node* root, int sum, int len, int& maxLen, int& maxSum) { // if true, then we have traversed a // root to leaf path if (!root) { // update maximum length and maximum sum // according to the given conditions if (maxLen < len) { maxLen = len; maxSum = sum; } else if (maxLen == len && maxSum < sum) maxSum = sum; return; } // recur for left subtree sumOfLongRootToLeafPath(root->left, sum + root->data, len + 1, maxLen, maxSum); // recur for right subtree sumOfLongRootToLeafPath(root->right, sum + root->data, len + 1, maxLen, maxSum); } // utility function to find the sum of nodes on // the longest path from root to leaf node int sumOfLongRootToLeafPathUtil(Node* root) { // if tree is NULL, then sum is 0 if (!root) return 0; int maxSum = INT_MIN, maxLen = 0; // finding the maximum sum 'maxSum' for the // maximum length root to leaf path sumOfLongRootToLeafPath(root, 0, 0, maxLen, maxSum); // required maximum sum return maxSum; } // Driver program to test above int main() { // binary tree formation Node* root = getNode(4); /* 4 */ root->left = getNode(2); /* / */ root->right = getNode(5); /* 2 5 */ root->left->left = getNode(7); /* / / */ root->left->right = getNode(1); /* 7 1 2 3 */ root->right->left = getNode(2); /* / */ root->right->right = getNode(3); /* 6 */ root->left->right->left = getNode(6); cout << "Sum = " << sumOfLongRootToLeafPathUtil(root); return 0; } |
Java
// Java implementation to find the sum of nodes // on the longest path from root to leaf node public class GFG { // Node of a binary tree static class Node { int data; Node left, right; Node(int data){ this.data = data; left = null; right = null; } } static int maxLen; static int maxSum; // function to find the sum of nodes on the // longest path from root to leaf node static void sumOfLongRootToLeafPath(Node root, int sum, int len) { // if true, then we have traversed a // root to leaf path if (root == null) { // update maximum length and maximum sum // according to the given conditions if (maxLen < len) { maxLen = len; maxSum = sum; } else if (maxLen == len && maxSum < sum) maxSum = sum; return; } // recur for left subtree sumOfLongRootToLeafPath(root.left, sum + root.data, len + 1); sumOfLongRootToLeafPath(root.right, sum + root.data, len + 1); } // utility function to find the sum of nodes on // the longest path from root to leaf node static int sumOfLongRootToLeafPathUtil(Node root) { // if tree is NULL, then sum is 0 if (root == null) return 0; maxSum = Integer.MIN_VALUE; maxLen = 0; // finding the maximum sum 'maxSum' for the // maximum length root to leaf path sumOfLongRootToLeafPath(root, 0, 0); // required maximum sum return maxSum; } // Driver program to test above public static void main(String args[]) { // binary tree formation Node root = new Node(4); /* 4 */ root.left = new Node(2); /* / */ root.right = new Node(5); /* 2 5 */ root.left.left = new Node(7); /* / / */ root.left.right = new Node(1); /* 7 1 2 3 */ root.right.left = new Node(2); /* / */ root.right.right = new Node(3); /* 6 */ root.left.right.left = new Node(6); System.out.println( "Sum = " + sumOfLongRootToLeafPathUtil(root)); } } // This code is contributed by Sumit Ghosh |
Python3
# Python3 implementation to find the # Sum of nodes on the longest path # from root to leaf nodes # function to get a new node class getNode: def __init__(self, data): # put in the data self.data = data self.left = self.right = None # function to find the Sum of nodes on the # longest path from root to leaf node def SumOfLongRootToLeafPath(root, Sum, Len, maxLen, maxSum): # if true, then we have traversed a # root to leaf path if (not root): # update maximum Length and maximum Sum # according to the given conditions if (maxLen[0] < Len): maxLen[0] = Len maxSum[0] = Sum elif (maxLen[0]== Len and maxSum[0] < Sum): maxSum[0] = Sum return # recur for left subtree SumOfLongRootToLeafPath(root.left, Sum + root.data, Len + 1, maxLen, maxSum) # recur for right subtree SumOfLongRootToLeafPath(root.right, Sum + root.data, Len + 1, maxLen, maxSum) # utility function to find the Sum of nodes on # the longest path from root to leaf node def SumOfLongRootToLeafPathUtil(root): # if tree is NULL, then Sum is 0 if (not root): return 0 maxSum = [-999999999999] maxLen = [0] # finding the maximum Sum 'maxSum' for # the maximum Length root to leaf path SumOfLongRootToLeafPath(root, 0, 0, maxLen, maxSum) # required maximum Sum return maxSum[0] # Driver Code if __name__ == '__main__': # binary tree formation root = getNode(4) # 4 root.left = getNode(2) # / root.right = getNode(5) # 2 5 root.left.left = getNode(7) # / / root.left.right = getNode(1) # 7 1 2 3 root.right.left = getNode(2) # / root.right.right = getNode(3) # 6 root.left.right.left = getNode(6) print("Sum = ", SumOfLongRootToLeafPathUtil(root)) # This code is contributed by PranchalK |
C#
using System; // c# implementation to find the sum of nodes // on the longest path from root to leaf node public class GFG { // Node of a binary tree public class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = null; right = null; } } public static int maxLen; public static int maxSum; // function to find the sum of nodes on the // longest path from root to leaf node public static void sumOfLongRootToLeafPath(Node root, int sum, int len) { // if true, then we have traversed a // root to leaf path if (root == null) { // update maximum length and maximum sum // according to the given conditions if (maxLen < len) { maxLen = len; maxSum = sum; } else if (maxLen == len && maxSum < sum) { maxSum = sum; } return; } // recur for left subtree sumOfLongRootToLeafPath(root.left, sum + root.data, len + 1); sumOfLongRootToLeafPath(root.right, sum + root.data, len + 1); } // utility function to find the sum of nodes on // the longest path from root to leaf node public static int sumOfLongRootToLeafPathUtil(Node root) { // if tree is NULL, then sum is 0 if (root == null) { return 0; } maxSum = int.MinValue; maxLen = 0; // finding the maximum sum 'maxSum' for the // maximum length root to leaf path sumOfLongRootToLeafPath(root, 0, 0); // required maximum sum return maxSum; } // Driver program to test above public static void Main(string[] args) { // binary tree formation Node root = new Node(4); // 4 root.left = new Node(2); // / root.right = new Node(5); // 2 5 root.left.left = new Node(7); // / / root.left.right = new Node(1); // 7 1 2 3 root.right.left = new Node(2); // / root.right.right = new Node(3); // 6 root.left.right.left = new Node(6); Console.WriteLine("Sum = " + sumOfLongRootToLeafPathUtil(root)); } } // This code is contributed by Shrikant13 |
Output:
Sum = 13
Time Complexity: O(n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments