Binary Tree Maximum Path Sum

• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxPathSum(TreeNode root) {
Int maxSum = new Int(Integer.MIN_VALUE);
getPathSumIncludingNode(root, maxSum);
return maxSum.val;
}

private PathSum getPathSumIncludingNode(TreeNode node, Int maxSum){
if(node == null) return null;

if(node.left ==null && node.right ==null){
maxSum.val = maxSum.val > node.val ?  maxSum.val : node.val;
return new PathSum(node.val, node.val);
}

PathSum leftSubTree = getPathSumIncludingNode(node.left, maxSum);
PathSum rightSubTree = getPathSumIncludingNode(node.right, maxSum);

int bothSubTreeSum = (leftSubTree !=null ? leftSubTree.oneSubTreeSum : 0) + (rightSubTree != null ?rightSubTree.oneSubTreeSum : 0) + node.val ;
int oneSubTreeSum = Math.max((leftSubTree !=null ? leftSubTree.oneSubTreeSum : 0), (rightSubTree != null ?rightSubTree.oneSubTreeSum : 0)) + node.val;
oneSubTreeSum = oneSubTreeSum > node.val ? oneSubTreeSum : node.val;
maxSum.val = maxSum.val > Math.max(bothSubTreeSum, oneSubTreeSum) ?  maxSum.val : Math.max(bothSubTreeSum, oneSubTreeSum);

return new PathSum(bothSubTreeSum, oneSubTreeSum);
}

static class PathSum{
int bothSubTreeSum;
int oneSubTreeSum;
public PathSum(int bothSubTreeSum, int oneSubTreeSum){
this.bothSubTreeSum = bothSubTreeSum;
this.oneSubTreeSum = oneSubTreeSum;
}
}

static class Int{
int val;
public Int(int val){
this.val = val;
}
}
}

• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int currentMax;
public int maxPathSum(TreeNode root) {
currentMax = root.val;
maxPathSumUTIL(root);
return currentMax;
}

public int maxPathSumUTIL(TreeNode root) {
if(root == null) return 0;

int leftMax = Math.max(0,maxPathSumUTIL(root.left));
int rightMax = Math.max(0,maxPathSumUTIL(root.right));

if(currentMax < (root.val + leftMax + rightMax))
currentMax = root.val + leftMax + rightMax;
return root.val + ((leftMax > rightMax)? leftMax : rightMax);
}
}

• Here is a solution in python.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

def pathSum(node):
"""
Returns tuple with sum of longest path including node, and maximum path sum in subtree.
"""
#      2
#     / \    => returns (7, 11) which is 5+2 for the right side, and 4+2+5 for the subtree.
#    4   5
if node is None:
return 0, None
# check left and right sides.
lsum, ltotal = pathSum(node.left)
rsum, rtotal = pathSum(node.right)
v = node.val
# longest path going maybe left, through node, and maybe right.
# either sides are optional since they may not contribute to increasing the value.
path = max(0, lsum) + v + max(0, rsum)
# maximum path sum for subtree, using 'or' to handle None.
# it's either the longest path we just calculated, or one from a left/right subtree.
total = max(path, ltotal or v, rtotal or v)
# longest path through node, but going only on one side (path continued in parent).
psum = v + max(0, lsum, rsum)
return psum, total

class Solution:
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
psum, total = pathSum(root)
return max(psum, total)

• using System;
class BinarySearchTree
{
private int max = int.MinValue;
Node root;
public class Node
{
public int data;
public Node right, left;
public Node(int d)
{
data = d;
right = null;
left = null;
}

}

public  int maxPathSum(Node root)
{
int rd = dfs(root);
return rd > max ? rd : max;
}
private int dfs(Node root)
{
if (root.left == null && root.right == null)
{
return root.data;
}
if (root.left == null && root.right != null)
{
int roPathMax = dfs(root.right);
max = roPathMax > max ? roPathMax : max;
return Math.Max(root.data, roPathMax + root.data);
}
if (root.right == null && root.left != null)
{
int loPathMax = dfs(root.left);
max = loPathMax > max ? loPathMax : max;
return Math.Max(root.data, loPathMax + root.data);
}
int lPathMax = dfs(root.left);
int rPathMax = dfs(root.right);
int closePathMax = lPathMax + rPathMax + root.data;

int innerMax = Math.Max(closePathMax, Math.Max(lPathMax, rPathMax));
max = innerMax > max ? innerMax : max;
return Math.Max(root.data, Math.Max(lPathMax + root.data, rPathMax + root.data));
}
static void Main()
{
BinarySearchTree BST = new BinarySearchTree();
BST.Insert(0);
BST.Insert(5);
BST.Insert(-4);
BST.Insert(-2);
BST.Insert(7);
BST.Insert(8);
BST.Insert(6);
//find max sum and  the subtree path
Console.WriteLine("Max pathSum of the given binary tree is " + BST.maxPathSum(BST.root));

}

public void Insert(int New)
{
Node N = new Node(New);
if(root==null)
{
root = N;
}
else
{
Node current = root;
Node parent;
while(true)
{
parent = current;
if(current.data > N.data)
{
current = current.left;
if(current==null)
{
parent.left = N;
break;
}
}
else
{
current = current.right;
if(current ==null)
{
parent.right = N;
break;
}
}
}
}
}

}

• Clean Python Solution:

class Solution(object):
def maxPathSum(self, root):
sums = []def dfs(root):
if root.left and root.right:
left = dfs(root.left)
right = dfs(root.right)
sums.append(root.val + left)
sums.append(root.val + right)
sums.append(root.val + left + right)
sums.append(root.val)
return max(root.val, root.val + left, root.val + right)
elif root.left:
left = dfs(root.left)
sums.append(root.val + left)
sums.append(root.val)
return max(root.val, root.val + left)
elif root.right:
right = dfs(root.right)
sums.append(root.val + right)
sums.append(root.val)
return max(root.val, root.val + right)
else:
sums.append(root.val)
return root.val
dfs(root)
return max(sums)

• class Node
{
int data;
Node left, right, nextRight;

Node(int item)
{
data = item;
left = right = nextRight = null;
}

}

class BinaryTreeSum
{
Node root;

/* Driver program to test above functions */
public static void main(String args[])
{
BinaryTreeSum tree = new BinaryTreeSum();
tree.root = new Node(26);
tree.root.left = new Node(10);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(6);
tree.root.right.right = new Node(3);

}

private static int addBt(Node node) {

int sum = 0;
if(node == null)
return sum;