Sum of nodes on the longest path from root to leaf node | C ++ implementation to find the sum of nodes on the longest path from root to leaf node ; Node of a binary tree ; function to get a new node ; allocate memory for the node ; put in the data ; function to find the sum of nodes on the longest path from root to leaf node ; if true , then we have traversed a root to leaf path ; update maximum length and maximum sum according to the given conditions ; recur for left subtree ; recur for right subtree ; utility function to find the sum of nodes on the longest path from root to leaf node ; if tree is NULL , then sum is 0 ; finding the maximum sum ' maxSum ' for the maximum length root to leaf path ; required maximum sum ; Driver program to test above ; binary tree formation ; 4 ; / \ ; 2 5 ; / \ / \ ; 7 1 2 3 ; 6
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * getNode ( int data ) { Node * newNode = ( Node * ) malloc ( sizeof ( Node ) ) ; newNode -> data = data ; newNode -> left = newNode -> right = NULL ; return newNode ; } void sumOfLongRootToLeafPath ( Node * root , int sum , int len , int & maxLen , int & maxSum ) { if ( ! root ) { if ( maxLen < len ) { maxLen = len ; maxSum = sum ; } else if ( maxLen == len && maxSum < sum ) maxSum = sum ; return ; } sumOfLongRootToLeafPath ( root -> left , sum + root -> data , len + 1 , maxLen , maxSum ) ; sumOfLongRootToLeafPath ( root -> right , sum + root -> data , len + 1 , maxLen , maxSum ) ; } int sumOfLongRootToLeafPathUtil ( Node * root ) { if ( ! root ) return 0 ; int maxSum = INT_MIN , maxLen = 0 ; sumOfLongRootToLeafPath ( root , 0 , 0 , maxLen , maxSum ) ; return maxSum ; } int main ( ) { Node * root = getNode ( 4 ) ; root -> left = getNode ( 2 ) ; root -> right = getNode ( 5 ) ; root -> left -> left = getNode ( 7 ) ; root -> left -> right = getNode ( 1 ) ; root -> right -> left = getNode ( 2 ) ; root -> right -> right = getNode ( 3 ) ; root -> left -> right -> left = getNode ( 6 ) ; cout << " Sum ▁ = ▁ " << sumOfLongRootToLeafPathUtil ( root ) ; return 0 ; }