Given the root of a binary tree, return the maximum sum of any non-empty path.

binary-tree-max-path.js

// Definition of a binary tree node
// class TreeNode {
//   constructor(data) {
//     this.data = data;
//     this.left = null;
//     this.right = null;
//   }
// }

import { TreeNode } from "./ds_v1/BinaryTree.js";

function maxPathSum(root) {
  // three things to keep in mind for each node
  // 1: calculate value when split is allowed (using current node as root)
  // 2: calculate value when split is not allowed (some other parent node is used as root)
  // 3: don't go down paths that decrease sum
  const { max } = maxPathSumRec(root, 0);
  return max;
}

function maxPathSumRec(node, max) {
  if (!node) {
    return { sum: 0, max };
  }
  const { sum: lSum, max: lMax } = maxPathSumRec(node.left, max);
  const { sum: rSum, max: rMax } = maxPathSumRec(node.right, max);

  // so parent node expects no-split value
  // the one that is chosen max between left and right no-split value + this node value
  // but we also need to calc split value, and compare it against max
  const sumSplit = node.data + Math.max(lSum, 0) + Math.max(rSum, 0);
  const sumNoSplit = node.data + Math.max(lSum, rSum, 0);

  return { sum: sumNoSplit, max: Math.max(lMax, rMax, sumSplit) };
}

export { maxPathSum };

// tc: O(n)
// sc: O(h) (balanced tree - logn, worst case n)