How to find the maximum path sum of a binary tree

12/05/2018

This is a good example for recursion. The algorithm needs to process all the nodes. If the sum of each sub tree is more that the current maximum we store the maximum. The algorithm is in o(n) where n is the number of nodes.

Create the following java file:

public class InterviewBTreeMaximumPathSum {

    int max = 0;
    
    public int maxPathSum(TreeNode a) {
	// Input validation
	if( a == null )
	    throw new IllegalArgumentException( "Result:" );
	
	max = 0;

	// Process the node
	maxPathSumNode(a);
	
	// Return the max value
	return max;
    }

    public int maxPathSumNode(TreeNode a) {
	if( a == null )
	    return 0;
	
	int left = maxPathSumNode(a.left);
	int right = maxPathSumNode(a.right);
	
	int tmpMax = left + right + a.val;
	
	if( tmpMax > max )
	    max = tmpMax;
	
	if( left > right )
	    return left + a.val; 
	
	return right + a.val;
    }

    public static void main(String[] argv) throws Exception {
	InterviewBTreeMaximumPathSum t = new InterviewBTreeMaximumPathSum();

	TreeNode in = new TreeNode(1);
	in.left = new TreeNode(2);
	in.right = new TreeNode(3);

	int res = t.maxPathSum(in);

	System.out.println("Input:" + in.toString());
	System.out.println("Result:" + res);
	
	
	in = new TreeNode(1);
	in.left = new TreeNode(1);
	in.left.left = new TreeNode(1);

	in.right = new TreeNode(2);
	in.right.left = new TreeNode(5);
	in.right.right = new TreeNode(3);
	
	res = t.maxPathSum(in);

	System.out.println("Input:" + in.toString());
	System.out.println("Result:" + res);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
	val = x;
    }
    
    public String toString(){
	String toReturn = "(value=" + String.valueOf(val);
	if( left != null || right != null )
	    toReturn = toReturn + ", left=" + left + ", right=" + right + " ";
	toReturn = toReturn + ")";
	
	return toReturn; 
    }
}

The output will be:

Input:(value=1, left=(value=2), right=(value=3) )
Result:6
Input:(value=1, left=(value=1, left=(value=1), right=null ), right=(value=2, left=(value=5), right=(value=3) ) )
Result:10

In the first example of the java code, the root node has the maximum path. In the second example a sub path has the maximum sum.

References:

Wikipedia Binary Tree

Recent Comments