Find maximum sum root to leaf path in a binary tree

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


       1
     /   \
    /     \
   2       3
  / \     / \
 8   4   5   6
    /   / \   \
  10   7   9   5

 


 
The problem can be divided further into two sub-problems –

1. Calculate maximum sum from root node to any leaf node in a binary tree

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 –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

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

Notify of
avatar
wpDiscuz