Sum of Longest Blood Line of Tree

Given a binary tree having n nodes. Find the sum of all nodes on the longest path from root to any leaf node. If two or more paths compete for the longest path, then the path having maximum sum of nodes will be considered.

Approach :

Recursively explore both the left and right subtrees.

When we reach a leaf node, we check :

• If the path length is greater than the current longest path length, update both the longest path length and the maximum sum.
• If the path length is equal to the longest, update the maximum sum if the current path sum is greater.

?? View Full Code??

void solve(Node* root, int sum, int &maxSum, int len, int &maxLen){
        
        if(root == NULL){
            if(len == maxLen){
                maxSum = max(sum, maxSum);
            }
            else if(len > maxLen){
                maxLen = len;
                maxSum = sum;
            }
            
            return ;
        }
        
        sum = sum + root->data;
        
        solve(root->left, sum, maxSum, len+1, maxLen);
        solve(root->right, sum, maxSum, len+1, maxLen);
    }
    
    int sumOfLongRootToLeafPath(Node *root)
    {
        int sum = 0;
        int maxSum = INT_MIN;
        
        int len = 0;
        int maxLen = 0;
        
        solve(root, sum, maxSum, len, maxLen);
        
        return maxSum;
    }        

Time Complexity : O(N)

Space Complexity : O(N)

?? View GitHub Repo ??