Binary Tree Maximum Path Sum

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left
(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int max_sum = INT_MIN;
        maxPathSumHelper(root, max_sum);
        return max_sum;
    }
    
    int maxPathSumHelper(TreeNode* root, int& max_sum) {
        if (root == nullptr) return 0;
        
        int left_sum = max(0, maxPathSumHelper(root->left, max_sum));
        int right_sum = max(0, maxPathSumHelper(root->right, max_sum));
        
        int total_sum = root->val + left_sum + right_sum;
        
        max_sum = max(max_sum, total_sum);
        
        return root->val + max(left_sum, right_sum);
    }
};

                                            
class Solution {
    int maxPathSum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        calculateSum(root);
        return maxPathSum;
    }
    
    private int calculateSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int left = Math.max(0, calculateSum(node.left));
        int right = Math.max(0, calculateSum(node.right));
        
        maxPathSum = Math.max(maxPathSum, left + right + node.val);
        
        return Math.max(left, right) + node.val;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxPathSum(struct TreeNode* root) {
    int max_sum = INT_MIN;
    
    int maxGain(struct TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        
        int left_gain = fmax(maxGain(node->left), 0);
        int right_gain = fmax(maxGain(node->right), 0);
        
        int node_path_sum = node->val + left_gain + right_gain;
        
        max_sum = fmax(max_sum, node_path_sum);
        
        return node->val + fmax(left_gain, right_gain);
    }
    
    maxGain(root);
    
    return max_sum;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    int maxPathSum = int.MinValue;

    public int MaxPathSum(TreeNode root) {
        CalculateMaxPathSum(root);
        return maxPathSum;
    }

    private int CalculateMaxPathSum(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSum = Math.Max(0, CalculateMaxPathSum(node.left));
        int rightSum = Math.Max(0, CalculateMaxPathSum(node.right));

        int currentPathSum = node.val + leftSum + rightSum;
        maxPathSum = Math.Max(maxPathSum, currentPathSum);

        return node.val + Math.Max(leftSum, rightSum);
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function(root) {
    let maxSum = -Infinity;
    
    const maxPathSumRecursive = (node) => {
        if (node === null) {
            return 0;
        }
        
        const leftSum = Math.max(maxPathSumRecursive(node.left), 0);
        const rightSum = Math.max(maxPathSumRecursive(node.right), 0);
        
        const currentSum = node.val + leftSum + rightSum;
        maxSum = Math.max(maxSum, currentSum);
        
        return node.val + Math.max(leftSum, rightSum);
    };
    
    maxPathSumRecursive(root);
    
    return maxSum;
};

                                            
function maxPathSum(root: TreeNode | null): number {
    let maxSum: number = -Infinity;
    
    const dfs = (node: TreeNode | null): number => {
        if (!node) return 0;
        
        const leftSum = Math.max(0, dfs(node.left));
        const rightSum = Math.max(0, dfs(node.right));
        
        maxSum = Math.max(maxSum, node.val + leftSum + rightSum);
        
        return node.val + Math.max(leftSum, rightSum);
    };
    
    dfs(root);
    
    return maxSum;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Integer
     */
    function maxPathSum($root) {
        $maxSum = PHP_INT_MIN;
        $this->maxPathSumHelper($root, $maxSum);
        return $maxSum;
    }
    
    function maxPathSumHelper($node, &$maxSum) {
        if ($node === null) return 0;
        
        $leftSum = max(0, $this->maxPathSumHelper($node->left, $maxSum));
        $rightSum = max(0, $this->maxPathSumHelper($node->right, $maxSum));
        
        $maxSum = max($maxSum, $node->val + $leftSum + $rightSum);
        
        return $node->val + max($leftSum, $rightSum);
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 */

class Solution {
    func maxPathSum(_ root: TreeNode?) -> Int {
        var maxSum = Int.min
        
        func maxGain(_ node: TreeNode?) -> Int {
            guard let node = node else { return 0 }
            
            let leftGain = max(maxGain(node.left), 0)
            let rightGain = max(maxGain(node.right), 0)
            
            let currentSum = node.val + leftGain + rightGain
            maxSum = max(maxSum, currentSum)
            
            return node.val + max(leftGain, rightGain)
        }
        
        _ = maxGain(root)
        return maxSum
    }
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    var maxSum = Int.MIN_VALUE
    
    fun maxPathSum(root: TreeNode?): Int {
        fun maxGain(node: TreeNode?): Int {
            if (node == null) return 0
            val leftGain = maxOf(0, maxGain(node.left))
            val rightGain = maxOf(0, maxGain(node.right))
            
            val newPathSum = node.`val` + leftGain + rightGain
            maxSum = maxOf(maxSum, newPathSum)
            
            return node.`val` + maxOf(leftGain, rightGain)
        }
        
        maxGain(root)
        
        return maxSum
    }
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode? left;
 *   TreeNode? right;
 *   TreeNode([this.val = 0, this.left, this.right]);
 * }
 */
class Solution {
  int maxPathSum(TreeNode? root) {
    int maxSum = -1001;
    
    int maxPath(TreeNode? node) {
      if (node == null) return 0;
      
      int leftSum = max(0, maxPath(node.left));
      int rightSum = max(0, maxPath(node.right));
      
      maxSum = max(maxSum, node.val + leftSum + rightSum);
      
      return node.val + max(leftSum, rightSum);
    }
    
    maxPath(root);
    
    return maxSum;
  }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func maxPathSum(root *TreeNode) int {
    var maxSum int
    maxSum = root.Val
    var maxPath func(node *TreeNode) int
    maxPath = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := max(maxPath(node.Left), 0)
        right := max(maxPath(node.Right), 0)
        maxSum = max(maxSum, node.Val+left+right)
        return node.Val + max(left, right)
    }

    maxPath(root)
    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer}
def max_path_sum(root)
    @max_sum = -Float::INFINITY
    
    def helper(node)
        return 0 if node.nil?
        
        left_sum = [helper(node.left), 0].max
        right_sum = [helper(node.right), 0].max
        
        current_sum = left_sum + right_sum + node.val
        @max_sum = [@max_sum, current_sum].max
        
        return [left_sum, right_sum].max + node.val
    end
    
    helper(root)
    
    return @max_sum
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: 
TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
    def maxPathSum(root: TreeNode): Int = {
        var maxSum = Int.MinValue
        
        def maxPathSumHelper(node: TreeNode): Int = {
            if (node == null) return 0
            
            val leftSum = math.max(0, maxPathSumHelper(node.left))
            val rightSum = math.max(0, maxPathSumHelper(node.right))
            
            maxSum = math.max(maxSum, node.value + leftSum + rightSum)
            
            math.max(leftSum, rightSum) + node.value
        }
        
        maxPathSumHelper(root)
        
        maxSum
    }
}

                                            
use std::cmp;
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut result = i32::MIN;
        Self::max_gain(&root, &mut result);
        result
    }
    
    fn max_gain(node: &Option<Rc<RefCell<TreeNode>>>, result: &mut i32) -> i32 {
        if let Some(n) = node {
            let n = n.borrow();
            let left_gain = cmp::max(0, Self::max_gain(&n.left, result));
            let right_gain = cmp::max(0, Self::max_gain(&n.right, result));
            
            let price_newpath = n.val + left_gain + right_gain;
            
            *result = cmp::max(*result, price_newpath);
            
            n.val + cmp::max(left_gain, right_gain)
        } else {
            0
        }
    }
}

To solve this coding challenge, the goal is to determine the maximum path sum in a binary tree. A path in a binary tree is defined as any sequence of nodes where each pair of adjacent nodes is connected and each node appears only once.

# Explanation

To effectively solve this problem, we can make use of Depth-First Search (DFS) to explore all potential paths in the binary tree. We need to compute the maximum path sum for each node, considering that node as the highest node in that path. The calculation involves these sub-components:

Recursive Function to Compute Max Path from Each Node:

* We will use a recursive function to compute the maximum path sum for the left and right subtrees of each node.

Handling Negative Sums:

* If a subtree path sum is negative, it should be ignored. Hence, we consider zero if the subtree path sum is negative. This is achieved by using the

max(value, 0)

function.

Updating Global Maximum:

* At each node, calculate the potential new path sum including the node itself and the left and right subtree sums. Update the global maximum variable if this path sum is higher.

In summary, the algorithm is structured as follows:

* Create a variable to store the global maximum path sum, initialized to a very small number (negative infinity).

* Define a recursive function that:

Returns 0 if it is called with a
null

node.
Computes the maximum path sums for the left and right children.
Ignores negative path sums by comparing with zero.
Updates the global maximum path sum considering the node and both its children.
Returns the maximum potential path sum from the current node considering one child path, for use by the node’s parent.

Detailed Steps in Pseudocode

                                            
# Function to compute the maximum path sum in the binary tree
function getMaxPathSum(root):
# Initialize global variable to track the maximum path sum
globalMaximumPathSum = -infinity

# Helper function to perform DFS and compute max path sum at each node
function maxPathFromNode(node):
# Base case: If node is null, return 0
if node == null:
return 0

# Recursively compute the max path sum for the left subtree
leftMaxSum = max(maxPathFromNode(node.left), 0)  # Ignore negative sums

# Recursively compute the max path sum for the right subtree
rightMaxSum = max(maxPathFromNode(node.right), 0)  # Ignore negative sums

# Current max path sum at this node considering both subtrees
currentPathSum = node.value + leftMaxSum + rightMaxSum

# Update the global maximum path sum if the current path sum is higher
globalMaximumPathSum = max(globalMaximumPathSum, currentPathSum)

# For the parent's perspective, only consider the larger sum path
return node.value + max(leftMaxSum, rightMaxSum)

# Begin DFS from the root
maxPathFromNode(root)

# Return the result: the maximum path sum encountered
return globalMaximumPathSum

# Example usage
# Given binary tree root, call getMaxPathSum(root)

# Explanation Expanded

Base Condition Handling:

* The recursive function

maxPathFromNode

returns zero if it encounters a

null

node. This means there is no path contribution from non-existent nodes.

Recursive Depth-First Search:

* For each node, the function recursively computes the maximum path sums for the left and right subtrees. It ensures that negative path sums are ignored, given they would decrease the overall path sum.

Computing Current Path Sum:

* For each node, compute the sum of the node's value, the maximum path sum from its left subtree, and the maximum path sum from its right subtree (

currentPathSum

). This value represents the best path sum passing through the node considering both children paths.

Updating Global Maximum:

* The global maximum path sum,

globalMaximumPathSum

, is updated if the

currentPathSum

from the current node is larger.

Returning Maximum Path for Parent Perspective:

* The function finally returns the maximum path sum from the node including one of its subtrees (whichever is larger) back to the parent node. This value will be used by the parent node’s computations. This is essentially

node.value + max(leftMaxSum, rightMaxSum)

By following these steps, we effectively explore all possible paths in the tree and determine the maximum path sum. The use of DFS ensures that we evaluate every possible path efficiently. The approach is robust and handles various constraints elegantly.