45464748495051525354555657585960616263646566676869

package main

import (
    "fmt"
    "math"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// maxPathSum finds the maximum path sum for the entire binary tree.
func maxPathSum(root *TreeNode) int {
    // Initialize maxi to the smallest possible int value
    maxi := math.MinInt

    // Recursive helper to compute max path sum and update maxi
    var findMaxPathSum func(node *TreeNode) int
    findMaxPathSum = func(node *TreeNode) int {
        // Base case: If the current node is nil, return 0
        if node == nil {
            return 0
        }

        // Calculate max path sum for left and right subtrees, ignore negatives
        leftMax := findMaxPathSum(node.Left)
        if leftMax < 0 {
            leftMax = 0
        }
        rightMax := findMaxPathSum(node.Right)
        if rightMax < 0 {
            rightMax = 0
        }

        // Update overall max path sum including current node
        sumThroughNode := leftMax + rightMax + node.Val
        if sumThroughNode > maxi {
            maxi = sumThroughNode
        }

        // Return max path including one branch plus current node
        if leftMax > rightMax {
            return leftMax + node.Val
        }
        return rightMax + node.Val
    }

    // Start recursion from root
    findMaxPathSum(root)
    return maxi
}

func main() {
    // Creating a sample binary tree
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}
    root.Left.Right.Right = &TreeNode{Val: 6}
    root.Left.Right.Right.Right = &TreeNode{Val: 7}

    // Finding and printing the maximum path sum
    result := maxPathSum(root)
    fmt.Println("Maximum Path Sum:", result)
}

Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the Binary Tree. This complexity arises from visiting each node exactly once during the recursive traversal.

Space Complexity: O(1) as no additional space or data structures are created that are proportional to the input size of the tree. O(H) Recursive Stack Auxiliary Space

1d:T587,class Solution { public: // Recursive function to find the maximum path sum // for a given subtree rooted at 'root' // The variable 'maxi' is a reference parameter // updated to store the maximum path sum encountered int findMaxPathSum(TreeNode* root, int& maxi) { // Base case: If the current node is null, return 0 if (root == nullptr) { return 0; } // Calculate the maximum path sum // for the left and right subtrees int leftMaxPath = std::max(0, findMaxPathSum(root->left, maxi)); int rightMaxPath = std::max(0, findMaxPathSum(root->right, maxi)); // Update the overall maximum // path sum including the current node maxi = std::max(maxi, leftMaxPath + rightMaxPath + root->data); /*Return the maximum sum considering only one branch (either left or right) along with the current node */ return std::max(leftMaxPath, rightMaxPath) + root->data; } // Function to find the maximum // path sum for the entire binary tree int maxPathSum(TreeNode* root) { // Initialize maxi to the // minimum possible integer value int maxi = INT_MIN; // Call the recursive function to // find the maximum path sum findMaxPathSum(root,