package algoexpert.hard;

/*

PROBLEM:

Find max path sum of a binary tree.

A path is collection of connected nodes where no node is connected to more than two nodes.

LOGIC:

Each node can either be

- root

- part of path

Maintain Max globalRoot

SOLUTION:

1. Recursion : time - O(n) | space - O(log n)

*/

public class MaxPathSum

{

static class BinaryTree {

public int value;

public BinaryTree left;

public BinaryTree right;

public BinaryTree(int value) {

this.value = value;

}

}

// returns { GlobalMaxAsRoot, maxInPath}

public static int [] traverse(BinaryTree node)

{

if (node == null) { return new int[] {0, 0}; }

int [] maxPathSumsLeft = traverse(node.left);

int [] maxPathSumsRight = traverse(node.right);

int maxAsRoot = node.value + maxPathSumsLeft[1] + maxPathSumsRight[1];

int maxInPath = node.value + Integer.max(maxPathSumsLeft[1], maxPathSumsRight[1]);

maxInPath = maxInPath < 0 ? 0 : maxInPath;

maxAsRoot = Integer.max( Integer.max(maxPathSumsLeft[0], maxPathSumsRight[0]), maxAsRoot);

return new int[] {maxAsRoot, maxInPath};

}

// main function

// time : O(n) | space : O(log n) - recursive stack

public static Integer maxPathSum(BinaryTree tree) {

int [] maxPathSums = traverse(tree);

return maxPathSums[0] > maxPathSums[1] ? maxPathSums[0] : maxPathSums[1];

}

}