Find the maximum sum leaf to root path in a Binary Tree | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; class node { public : int data ; node * left ; node * right ; } ; bool printPath ( node * root , node * target_leaf ) { if ( root == NULL ) return false ; if ( root == target_leaf || printPath ( root -> left , target_leaf ) || printPath ( root -> right , target_leaf ) ) { cout << root -> data << " ▁ " ; return true ; } return false ; } void getTargetLeaf ( node * Node , int * max_sum_ref , int curr_sum , 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 ( node * Node ) { if ( Node == NULL ) return 0 ; node * target_leaf ; int max_sum = INT_MIN ; getTargetLeaf ( Node , & max_sum , 0 , & target_leaf ) ; printPath ( Node , target_leaf ) ; return max_sum ; } node * newNode ( int data ) { node * temp = new node ; temp -> data = data ; temp -> left = NULL ; temp -> right = NULL ; return temp ; } int main ( ) { node * root = NULL ; root = newNode ( 10 ) ; root -> left = newNode ( -2 ) ; root -> right = newNode ( 7 ) ; root -> left -> left = newNode ( 8 ) ; root -> left -> right = newNode ( -4 ) ; cout << " Following ▁ are ▁ the ▁ nodes ▁ on ▁ the ▁ maximum ▁ " " sum ▁ path ▁ STRNEWLINE " ; int sum = maxSumPath ( root ) ; cout << " Sum of the nodes is " return 0 ; }