Max Path Sum In Binary Tree

• Time : O(n)
• Space : O(1)

#include <vector>
using namespace std;

class BinaryTree {
public:
  int value;
  BinaryTree *left;
  BinaryTree *right;

  BinaryTree(int value);
  void insert(vector<int> values, int i = 0);
};

int helper(BinaryTree tree, int& res) {
	int path = tree.value;
	if(tree.left && tree.right) {
		int l = helper(*tree.left, res);
		int r = helper(*tree.right, res);
		res = max({res, path, l + path, r + path, l + r + path});
		return max({path, l + path, r + path, 0});
	} else if(tree.left) {
		int l = helper(*tree.left, res);
		res = max({res, l + path, path});
		return max({0, path, l + path});
	} else if(tree.right) {
		int r = helper(*tree.right, res);
		res = max({res, r + path, path});
		return max({0, path, r + path});
	} else {
		res = max(res, path);
		return max(0,path);
	}
}

int maxPathSum(BinaryTree tree) {
  int res = INT_MIN;
	helper(tree, res);
  return res;
}