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


          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(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 –
 

Download   Run Complete Code

 
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 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of