# Find maximum sum root to leaf path in a binary tree

Given a binary tree, write an efficient algorithm to find maximum sum root to leaf path i.e. maximum sum path from root node to any leaf node in it.

For example, consider below tree.

Maximum sum is 18
Maximum sum path is: 1 3 5 9

The problem can be divided further into two sub-problems –

1. Calculate maximum sum from root node to any leaf node in a binary tree

2. Print root-to-leaf path having maximum sum in a binary tree

We can solve both problems in linear time by traversing the tree in bottom-up manner (postorder fashion). Below is the simple implementation of it –

C++ implementation –

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
Akash KAndpal

Another way to implement it ::
int getMaxSum(struct node * root){

if(root == NULL){
return 0;
}

if(root->left == NULL && root->right == NULL){
return root->data;
}

return root->data + max(getMaxSum(root->left),getMaxSum(root->right));

}

Guest
Akash KAndpal

Simple Java Code for calculating max sum:-

public static int maxSum(Tree root,int sum){

if(root == null){
return 0;
}

sum = sum + root.data;
int lsum = maxSum(root.left,sum);
int rsum = maxSum(root.right,sum);

int greaterSum = Math.max(lsum,rsum);
int max = Math.max(greaterSum,sum);
sum = sum – root.data;
return max;
}