Maximum Path Sum in a Binary Tree

Given a binary tree, write a program to find the maximum path sum. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Input/Output Examples

plaintext
Example 1:
Input:

     1
    / \
   2   3

Output:
6
Explanation: The maximum path sum is obtained by adding 2 + 1 + 3, which equals 6.

Example 2:
Input:

     -10
     /  \
    9   20
        / \
       15  7

Output:
42
Explanation: The maximum path sum is obtained by adding 15 + 20 + 7, which equals 42.

Approach to Find the Maximum Path Sum in a Binary Tree

  1. Recursive Depth-First Search (DFS) Traversal:
    • For each node, we calculate the maximum path sum by considering two possibilities:
      • The path going through the left child.
      • The path going through the right child.
    • The contribution of a node to the path is the node’s value plus the maximum path sum through either of its children (if the path through that child increases the sum).
  2. Global Maximum Path Sum:
    • While calculating the path sums recursively, keep track of a global variable to store the maximum path sum encountered so far. This value will be updated when the path through a particular node (which may include both left and right subtrees) exceeds the current global maximum.
  3. Edge Case:
    • If the tree is empty, return 0 as the maximum path sum.

C++ Program to Find the Maximum Path Sum in a Binary Tree

cpp
#include <iostream>
#include <climits>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Helper function to calculate maximum path sum
int maxPathSumUtil(TreeNode* root, int& maxSum) {
    if (root == NULL) {
        return 0;
    }

    // Calculate the maximum path sum going through the left and right children
    int leftMax = max(0, maxPathSumUtil(root->left, maxSum));  // Ignore negative paths
    int rightMax = max(0, maxPathSumUtil(root->right, maxSum));  // Ignore negative paths

    // Update the maximum sum encountered so far (considering both children)
    maxSum = max(maxSum, leftMax + rightMax + root->data);

    // Return the maximum path sum including the current node
    return root->data + max(leftMax, rightMax);
}

// Function to find the maximum path sum in a binary tree
int maxPathSum(TreeNode* root) {
    int maxSum = INT_MIN;
    maxPathSumUtil(root, maxSum);
    return maxSum;
}

int main() {
    // Create a sample tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    // Find and print the maximum path sum
    cout << "Maximum Path Sum: " << maxPathSum(root) << endl;

    return 0;
}

Java Program to Find the Maximum Path Sum in a Binary Tree

java
// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

public class MaxPathSumBinaryTree {

    // Helper function to calculate maximum path sum
    private static int maxPathSumUtil(TreeNode root, int[] maxSum) {
        if (root == null) {
            return 0;
        }

        // Calculate the maximum path sum going through the left and right children
        int leftMax = Math.max(0, maxPathSumUtil(root.left, maxSum));  // Ignore negative paths
        int rightMax = Math.max(0, maxPathSumUtil(root.right, maxSum));  // Ignore negative paths

        // Update the maximum sum encountered so far (considering both children)
        maxSum[0] = Math.max(maxSum[0], leftMax + rightMax + root.data);

        // Return the maximum path sum including the current node
        return root.data + Math.max(leftMax, rightMax);
    }

    // Function to find the maximum path sum in a binary tree
    public static int maxPathSum(TreeNode root) {
        int[] maxSum = new int[1];
        maxSum[0] = Integer.MIN_VALUE;
        maxPathSumUtil(root, maxSum);
        return maxSum[0];
    }

    public static void main(String[] args) {
        // Create a sample tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        // Find and print the maximum path sum
        System.out.println("Maximum Path Sum: " + maxPathSum(root));
    }
}

Python Program to Find the Maximum Path Sum in a Binary Tree

python
# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Helper function to calculate maximum path sum
def max_path_sum_util(root, max_sum):
    if root is None:
        return 0

    # Calculate the maximum path sum going through the left and right children
    left_max = max(0, max_path_sum_util(root.left, max_sum))  # Ignore negative paths
    right_max = max(0, max_path_sum_util(root.right, max_sum))  # Ignore negative paths

    # Update the maximum sum encountered so far (considering both children)
    max_sum[0] = max(max_sum[0], left_max + right_max + root.data)

    # Return the maximum path sum including the current node
    return root.data + max(left_max, right_max)

# Function to find the maximum path sum in a binary tree
def max_path_sum(root):
    max_sum = [-float('inf')]
    max_path_sum_util(root, max_sum)
    return max_sum[0]

# Example usage
if __name__ == "__main__":
    # Create a sample tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)

    # Find and print the maximum path sum
    print("Maximum Path Sum:", max_path_sum(root))
  • Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited once during the recursive traversal.
  • Space Complexity: O(h), where h is the height of the tree. This space is required for the recursive call stack. In the worst case (for a skewed tree), the space complexity is O(n).

DSA

2564

447

Related Articles