How To Find maximum sum path between two leaves in a binary tree?

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

For example, consider below tree.
The maximum sum path between two leaves is highlighted below having sum 22
Maximum Sum Path
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(N2) 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 patof 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 path 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 –
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.


Popular posts from this blog

How to change this to <%Html.ActionLink%> in my mvc application ?