Largest Tree Sum Path - Google Top Interview Questions

                        Solution in C++ :

int helper(Tree* root, int& ans) {
    if (!root) return 0;
    int a = helper(root->left, ans);
    int b = helper(root->right, ans);
    ans = max(ans, max(root->val + a + b, root->val));
    return max(a + root->val, b + root->val);
}

int solve(Tree* root) {
    int ans = INT_MIN;
    helper(root, ans);
    return ans;
}
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    private int ans = Integer.MIN_VALUE;
    public int solve(Tree root) {
        traversal(root);
        return ans;
    }

    private int traversal(Tree root) {
        if (root == null) {
            return 0;
        }
        int left = traversal(root.left);
        int right = traversal(root.right);

        int onePath = Math.max(Math.max(left, right) + root.val, root.val);
        int topSum = Math.max(onePath, left + right + root.val);
        ans = Math.max(ans, topSum);

        return onePath;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, root):
        ans = -math.inf

        def dfs(root):
            if root is None:
                return 0

            left = dfs(root.left)
            right = dfs(root.right)

            single = max(left + root.val, right + root.val, root.val)

            top = max(single, left + right + root.val)

            nonlocal ans
            ans = max(ans, top)

            return single

        dfs(root)
        return ans