Binary Tree Maximum Path Sum - Java Solution

1. Introduction

In this post, we delve into a common problem in binary tree algorithms: finding the maximum path sum in a binary tree. This problem entails calculating the highest possible sum of values from any path in the tree, where a path is defined as a sequence of connected nodes.

Problem

Given the root of a binary tree, the objective is to find the maximum path sum of any non-empty path within the tree. A path is a sequence of nodes where each adjacent pair is connected by an edge, and each node can appear at most once in the path.

2. Solution Steps

1. Use a recursive approach to traverse the tree.

2. At each node, calculate the maximum path sum as the node's value plus the maximum path sums of its left and right subtrees.

3. Update a global variable to keep track of the maximum path sum found so far.

4. Handle edge cases such as negative path sums.

5. Return the maximum path sum found.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreeMaximumPathSum {
    private static int maxSum;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(maxPathSum(root)); // Test the function
    }

    // Function to find the maximum path sum in a binary tree
    public static int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        pathSum(root);
        return maxSum;
    }

    // Helper function to calculate path sum recursively
    private static int pathSum(TreeNode node) {
        if (node == null) return 0;

        int left = Math.max(0, pathSum(node.left)); // Maximum path sum on the left
        int right = Math.max(0, pathSum(node.right)); // Maximum path sum on the right

        maxSum = Math.max(maxSum, left + right + node.val); // Update maxSum

        return Math.max(left, right) + node.val; // Return max path sum rooted at this node
    }
}

Output:

6

Explanation:

1. maxPathSum: This function initializes maxSum to the smallest possible integer value and calls pathSum to start the recursive process.

2. pathSum: A recursive helper function that calculates the maximum path sum rooted at each node. It computes the maximum path sum for the left and right subtrees and updates maxSum with the larger of the two plus the current node's value.

3. The function returns the maximum path sum starting from the current node to its parent node.

4. The main function prints the maximum path sum for the given binary tree.

5. This approach ensures all possible paths are considered, and the maximum path sum is calculated efficiently.