import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    
    public TreeNode(int val) {
        this.val = val;
    }
}

class FindMaxSum {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(100);
        root.left.left = new TreeNode(5);
        
        System.out.println("Max sum is: " + getMaxSum(root));
    }

    public static int getMaxSum(TreeNode root) {
        Map<TreeNode, Integer> memo = new HashMap<>();
        return dfs(root, memo);
    }

    private static int dfs(TreeNode node, Map<TreeNode, Integer> memo) {
        if (node == null) return 0;
        if (memo.containsKey(node)) return memo.get(node);

        // If we include the current node
        int include = node.val;
        if (node.left != null) {
            include += dfs(node.left.left, memo) + dfs(node.left.right, memo);
        }
        if (node.right != null) {
            include += dfs(node.right.left, memo) + dfs(node.right.right, memo);
        }

        // If we exclude the current node
        int exclude = dfs(node.left, memo) + dfs(node.right, memo);

        // Store the maximum result in memo
        int result = Math.max(include, exclude);
        memo.put(node, result);
        
        return result;
    }
}