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

1

/ \

/ \

2 **3**

\ **/ \**

-4 **5 6**

/ **\**

7 **8**

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