text: Find the maximum sum leaf to root path in a Binary Tree | C program to find maximum sum leaf to root path in Binary Tree ; A tree node structure ; A utility function that prints all nodes on the path from root to target_leaf ; base case ; return true if this node is the target_leaf or target leaf is present in one of its descendants ; This function Sets the target_leaf_ref to refer the leaf node of the maximum path sum . Also , returns the max_sum using max_sum_ref ; Update current sum to hold sum of nodes on path from root to this node ; If this is a leaf node and path to this node has maximum sum so far , then make this node target_leaf ; If this is not a leaf node , then recur down to find the target_leaf ; Returns the maximum sum and prints the nodes on max sum path ; base case ; find the target leaf and maximum sum ; print the path from root to the target leaf ; return maximum sum ; Utility function to create a new Binary Tree node ; Driver function to test above functions
code: #include <limits.h> NEW_LINE #include <stdbool.h> NEW_LINE #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct node { int data ; struct node * left ; struct node * right ; } ; bool printPath ( struct node * root , struct node * target_leaf ) { if ( root == NULL ) return false ; if ( root == target_leaf || printPath ( root -> left , target_leaf ) || printPath ( root -> right , target_leaf ) ) { printf ( " % d ▁ " , root -> data ) ; return true ; } return false ; } void getTargetLeaf ( struct node * node , int * max_sum_ref , int curr_sum , struct node * * target_leaf_ref ) { if ( node == NULL ) return ; curr_sum = curr_sum + node -> data ; if ( node -> left == NULL && node -> right == NULL ) { if ( curr_sum > * max_sum_ref ) { * max_sum_ref = curr_sum ; * target_leaf_ref = node ; } } getTargetLeaf ( node -> left , max_sum_ref , curr_sum , target_leaf_ref ) ; getTargetLeaf ( node -> right , max_sum_ref , curr_sum , target_leaf_ref ) ; } int maxSumPath ( struct node * node ) { if ( node == NULL ) return 0 ; struct node * target_leaf ; int max_sum = INT_MIN ; getTargetLeaf ( node , & max_sum , 0 , & target_leaf ) ; printPath ( node , target_leaf ) ; return max_sum ; } struct node * newNode ( int data ) { struct node * temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ; temp -> data = data ; temp -> left = NULL ; temp -> right = NULL ; return temp ; } int main ( ) { struct node * root = NULL ; root = newNode ( 10 ) ; root -> left = newNode ( -2 ) ; root -> right = newNode ( 7 ) ; root -> left -> left = newNode ( 8 ) ; root -> left -> right = newNode ( -4 ) ; printf ( " Following ▁ are ▁ the ▁ nodes ▁ on ▁ the ▁ maximum ▁ " " sum ▁ path ▁ STRNEWLINE " ) ; int sum = maxSumPath ( root ) ; printf ( " Sum of the nodes is % d " , sum ) ; getchar ( ) ; return 0 ; }