PROBLEM DESCRIPTION
Given a binary tree, return its max path sum.
SOLUTION
The apprach to this problem is similar to Binary Tree Diameter. We keep a track of two things, the sum in LST and the sum in RST, and return the max between them when calling the function recursively.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.*;
class Program {
public static int maxSum = Integer.MIN_VALUE;
public static int maxPathSumHelper(BinaryTree tree) {
if(tree == null) return 0;
int left = maxPathSumHelper(tree.left) + tree.value;
int right = maxPathSumHelper(tree.right) + tree.value;
//since tree.value has been added twice so we decrease it once to get the actual sum
if(left+right-tree.value > maxSum){
maxSum = left+right-tree.value;
}
//if sum on LST or RST can be -ve. So the previos block will actually give us a lower total sum. Hence, we need to check the sum only on the LST and only on the RST as well.
if(left > maxSum){
maxSum = left;
}
if(right > maxSum){
maxSum = right;
}
//Important: we are not returning the total path sum, but rather the max between left and right sub tree
return Math.max(left, right);
}
public static int maxPathSum(BinaryTree tree) {
maxSum = Integer.MIN_VALUE;
maxPathSumHelper(tree);
return maxSum;
}
static class BinaryTree {
public int value;
public BinaryTree left;
public BinaryTree right;
public BinaryTree(int value) {
this.value = value;
}
}
}