A binary tree is given, the task is to return sum of nodes of the longest path from root to leaf.
If there are more than one paths with same length than return max-sum out of them.
Solutions
Method 1: Recursion
We have declared two variables "sumSoFar = 0" and "maxLevel = -1", the idea is to traverse the tree in level-order and pass a variable to identify current level.
In any recurrence if we find that the "level" is more than the "maxLevel", we update "sumSoFar" and "maxLevel" with current "sum" and "level".
If level is same but current sum is greater than the "sumSoFar", we update the "sumSoFar" only.
Keep on recurring same process for left and right sub-trees.
Complexity
The time complexity of this solution is O(n) and space complexity is O(n) due to call stack.