Max Path Sum In Binary Tree

• h, h

function maxPathSum(tree) {

  const max = {
    sum: -Infinity,
  };

  findMaxSum(tree, max);
  return max.sum;
}

function findMaxSum(node, max) {
  if (node === null) {
    return 0;
  }

  const left = findMaxSum(node.left, max);
  const right = findMaxSum(node.right, max);

  const currentValue = node.value;
  const pathMax = left + right + node.value;
  max.sum = Math.max(max.sum, pathMax, currentValue, left + currentValue, right + currentValue);
  
  return Math.max(left, right) + currentValue;
}

exports.maxPathSum = maxPathSum;