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

     /   \
    /     \
   2       3
  / \     / \
 8   4   5   6
    /   / \   \
  10   7   9   5


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).

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of
Sort by:   newest | oldest | most voted
Akash KAndpal
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;

Akash KAndpal
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)); }