Max sum path from node to node

#1

In this question the last statement

return max(left,right,0) + root->val
'yeh waala statement sirf jo poore tree ka root hai uske liye implement horha hai na?Jab saare subtrees ke recursive calls khatam hojaayenge?

and also is question mei humne assume kiya hai ki jo poore tree ka node hai(jaise ki 10 ) is always positive?

#2

Hello @aryamaan1011,

For finding the maximum sum path, you are performing four computations in each function call:

  1. return_val_left_subtree + root->data + return_val_right_subtree
  2. return_val_left_subtree + root->data
  3. root->data + return_val_right_subtree
  4. root->data

But, while returning a value, you have to compare only 2, 3 and 4th.
Reason:
Let us consider an example:
_____________ 1
_______2
____3 ______20

When you are at 2, maximum sum path will have value 25 for point 1.
But, when you will return a value for the parent, you have to consider one of the two possible paths i.e.
either 2->3 or 2->20
reason:
Because 1 cannot have both 3 and 20 in the same path.
So, you choose to return the path with maximum sum.

Also for the cases like:
_____________ 1
_______2
____-3 ______-20

You will return root->data

Finally, you return max(2.,3.,4.)

Hope, this would help.
Give a like if you are satisfied.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.