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 –
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 –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to print root-to-leaf path having given sum in a binary tree bool printPath (Node *root, int sum) { // base case if (sum == 0) return true; // base case if (root == nullptr) return false; // recurse for left and right subtree with reduced sum bool left = printPath(root->left, sum - root->data); bool right = printPath(root->right, sum - root->data); // print current node if it lies on path having given sum if (left || right) cout << root->data << " "; return left || right; } // Function to calculate maximum root-to-leaf sum in a binary tree int rootToLeafSum(Node* root) { // base case: tree is empty if (root == nullptr) return 0; // calculate maximum node-to-leaf sum for left child int left = rootToLeafSum(root->left); // calculate maximum node-to-leaf sum for right child int right = rootToLeafSum(root->right); // consider maximum sum child return (left > right ? left : right) + root->data; } // Function to print maximum sum root-to-leaf path in a given binary tree void findMaxSumPath(Node *root) { int sum = rootToLeafSum(root); cout << "Maximum sum is " << sum << endl; cout << "Maximum sum path is: "; printPath(root, sum); } |
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
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));
}
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;
}