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 Root to Leaf Path

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 –

Download   Run Complete Code

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

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

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 🙂

Leave a Reply

newest oldest most voted
Notify of
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));


Akash KAndpal

Simple Java Code for calculating max sum:-

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

if(root == null){
return 0;

sum = sum +;
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 –;
return max;