maxPathSum.ts

// Option utils
type Some<T> = {
  type: 'some';
  value: T;
};
type None = {
  type: 'none';
};
type Option<T> = Some<T> | None;

const some = <T>(value: T): Option<T> => ({type: 'some', value});
const none: None = {type: 'none'};

const getOrElse = <T>(option: Option<T>, defaultValue: T): T => {
  if (option.type === 'some') {
    return option.value;
  } else {
    return defaultValue;
  }
};

const map = <T, U>(option: Option<T>, mapper: (t: T) => U): Option<U> => {
  if (option.type === 'some') {
    return some(mapper(option.value));
  } else {
    return none;
  }
};

// Binary tree utils
type BinaryTree<T> = {
  payload: T;
  left: Option<BinaryTree<T>>;
  right: Option<BinaryTree<T>>;
};
type NumberBinaryTree = BinaryTree<number>;

const bt = (
  payload: number,
  left?: NumberBinaryTree,
  right?: NumberBinaryTree,
): NumberBinaryTree => {
  return {
    payload,
    left: left === undefined ? none : some(left),
    right: right === undefined ? none : some(right),
  };
};

// Code
const maxPathSum = (tree: NumberBinaryTree): number => {
  // Six cases, viewing left-to-right:
  // 1. Path starts on left, ends on right
  // 2. Path starts on left, ends on root
  // 3. Path starts on left, ends on left
  // 4. Path starts on root, ends on root (zero-length, zero sum)
  // 5. Path starts on root, ends on right
  // 6. Path starts on right, ends on right
  // Note that the minimum is always zero because of 4.
  const {payload, left, right} = tree;
  const leftRootSum = getOrElse(map(left, maxPathSumFromRoot), 0);
  const rightRootSum = getOrElse(map(right, maxPathSumFromRoot), 0);

  const sum1 = leftRootSum + payload + rightRootSum;
  const sum2 = leftRootSum + payload;
  const sum3 = getOrElse(map(left, maxPathSum), 0);
  const sum4 = 0;
  const sum5 = payload + rightRootSum;
  const sum6 = getOrElse(map(right, maxPathSum), 0);

  return Math.max(sum1, sum2, sum3, sum4, sum5, sum6);
};

const maxPathSumFromRoot = (tree: NumberBinaryTree): number => {
  const {payload, left, right} = tree;
  const leftSum = map(map(left, maxPathSumFromRoot), l => l + payload);
  const rightSum = map(map(right, maxPathSumFromRoot), r => r + payload);

  return Math.max(
    payload,
    getOrElse(leftSum, payload),
    getOrElse(rightSum, payload),
  );
};

// Tests
const assert = (value: boolean, message: string) => {
  if (!value) {
    console.log(`Failed assertion: #{message}`);
  } else {
    console.log('Pass!');
  }
};

const it = (description: string, test: () => void) => {
  console.log(description);
  test();
  console.log();
};

it('provided example', () => {
  const tree = bt(
    10,
    bt(3, bt(20), bt(1)),
    bt(10, undefined, bt(-20, bt(5), bt(2))),
  );
  assert(maxPathSum(tree) == 43, 'Expected maxPathSum=43');
});

it('tree of only negative numbers', () => {
  const tree = bt(-1, bt(-1, bt(-1), bt(-1)), bt(-1, bt(-1), bt(-1)));
  assert(maxPathSum(tree) == 0, 'Expected maxPathSum=0');
});

it('tree where path is only on left side', () => {
  // Build a tree that's positive but nested deeply on the left under a bunch
  // of value=-1 nodes
  const positiveTree = bt(2, bt(3), bt(1));
  const tree = bt(-1, bt(-1, bt(-1, bt(-1, positiveTree))), bt(2));
  assert(maxPathSum(tree) == 2 + 3 + 1, 'Expected maxPathSum=6');
});

it('tree where path is on left side and includes root', () => {
  // In this example, we have to "dig" through two -1 to get to the value=3
  // node. We should also ignore the two value=2 nodes because they're not
  // worth it
  const tree = bt(3, bt(-1, bt(-1, bt(3), bt(2))), bt(-3, bt(2)));
  assert(maxPathSum(tree) == 3 - 1 - 1 + 3, 'Expected maxPathSum=4');
});