5.3 Path Sum

Demo: Binary Tree Maximum Path Sum — LC 124 (Hard — Microsoft/Meta High)

Statement (Demo): binary tree-এর root দেওয়া — যেকোনো node থেকে যেকোনো node-এ (একটা node-ও হতে পারে) যাওয়ার path-এর maximum sum বের করুন। Path একই node দুইবার visit করতে পারবে না। উদাহরণ: root=[-10,9,20,null,null,15,7] → 42 (15→20→7) | ⚡ n ≤ 3×10⁴, -1000 ≤ val ≤ 1000

Approach: প্রতিটা নোডে দুটো হিসাব: (১) এই নোডে বাঁক নেওয়া path-এর যোগফল = node + leftGain + rightGain → global best; (২) parent-কে ফেরত দেওয়া যায় শুধু এক দিকের সেরা branch = node + max(leftGain, rightGain)। Negative branch নেবেন না (max(gain, 0))।

function maxPathSum(root) {
  let best = -Infinity;
  const gain = (node) => {
    if (!node) return 0;
    const left = Math.max(gain(node.left), 0); // negative হলে বাদ
    const right = Math.max(gain(node.right), 0);
    best = Math.max(best, node.val + left + right); // এখানে বাঁক
    return node.val + Math.max(left, right); // parent-কে এক দিক
  };
  gain(root);
  return best;
}

Complexity: Time O(n), Space O(h) recursion