Given a binary tree, write an efficient algorithm to find maximum sum path between any two leaves in it.

The maximum sum path between two leaves is highlighted below having sum 22

Simple solution would be to calculate *maximum sum node-to-leaf path* starting from the left child and right child for every node in the tree. Then the *maximum sum path between two leaves* that passes through a node has value equal to *maximum sum node-to-leaf path* of its left and right child plus the node’s value. Finally, we consider maximum value among all *maximum sum paths* found for every node in the tree. The time complexity of this solution is `O(N ^{2})` as there are N nodes in the tree and for every node we are calculating

*maximum sum node-to-leaf path*of its left subtree and right subtree that takes

`O(N)`time.

We can solve this problem in **linear time** by traversing the tree in bottom-up manner. Instead of calculating *maximum sum node-to-leaf pat**h *of left child and right child for every node in the tree, we can calculate the *maximum sum path between two leaves* that passes through a node in constant time. The idea is to start from the bottom of the tree and return *maximum sum node-to-leaf pat**h* of each node to its parent node. We pass *maximum sum path* by reference to the function (instead of returning it) and update its value within the function itself using return value of left and right subtree.

**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 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Recursive function to find the maximum sum path between two leaves // in a binary tree int maxSumPath(Node *root, int& max_sum) { // base case: empty tree if (root == nullptr) return 0; // find maximum sum node-to-leaf path starting from left child int left = maxSumPath(root->left, max_sum); // find maximum sum node-to-leaf path starting from right child int right = maxSumPath(root->right, max_sum); // find maximum sum path "through" the current node int cur_sum = left + right + root->data; // update maximum sum path found so far (Note that maximum sum path // "excluding" the current node in subtree rooted at current node // is already updated as we're doing post-order traversal) max_sum = max(cur_sum, max_sum); // important - return maximum sum node-to-leaf path starting from // current node return max(left, right) + root->data; } // Function to return maximum sum path between two leaves in a binary tree int maxSumPath(Node* root) { int max_sum = INT_MIN; maxSumPath(root, max_sum); return max_sum; } |

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

**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