Maximum Path Sum in a Binary Tree

Given a binary tree, find the maximum path sum .

A path is a sequence of nodes connected by edges.

You can start from any node and go to any node in the tree as long as they are connected by edges.

Also the same node cannot be present more than one in the sequence.

Consider the given tree:

Few of the valid paths in the above tree are:

9 -> -10

9 -> -10 -> 20 -> 15

9 -> -10 -> 20 -> 7

9 -> -10 -> 20

15 ->20 -> 7

The below path is invalid:

15 -> 20 -> 7 -> 20 -> -10

Because 20 is repeated

The path with maximum path sum in the above tree is :

15 -> 20 -> 7

the sum is 42

So output is 42

Try out the solution here:

https://leetcode.com/problems/binary-tree-maximum-path-sum/

Solution:

Hint: Use Recursion.

At any node ,

You can calculate the maximum sum by adding:

The node value ,

The maximum sum of the left subtree and

The maximum sum of the right subtree

The maximum sum of the left and right subtrees are calculated recursively.

You calculate this maximum sum for each node and then return the maximum of the maximum sums.

There are few points to note here:

While calculating the maximum value of the left subtree or the right subtree , if the sum is less than 0 , then the final sum is going to get reduced, so you can ignore it.

You do that by comparing the left or right subtree sum with 0.

You can use the below code:

int left = Math.max(0,sum(node.left));

where sum(node.left) is the recursive function invoked on the left node of the current node.

Also while you recursively calculate the sum , you should choose the maximum of the left subtree sum or the right subtree sum since both of them cannot be included in the same path sequence

This is done using the below return statement in the recursive call:

        return node.val + Math.max(left,right );

where left and right sums are calculated as explained earlier.

Here is the entire code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        
        
       sum(root); 
       
        
        
        return max;
    }
    
    
    public int sum(TreeNode node){
        
        if(node == null) return 0;
        
        int left = Math.max(0,sum(node.left));
        
        int right = Math.max (0, sum(node.right));
        int sum =  node.val + left + right ; 
        
        max = Math.max(sum,max);
        
        return node.val + Math.max(left,right );
    }
}

Algorithm:

  1. Initialize maximum sum value to the lowest integer value
  2. Do a recursive call on the root node with the below logic:
  3. If the root node is null return 0
  4. Else find the sum of the left subtree (return 0 if it is negative)
  5. Find the sum of the right subtree (return 0 if it is negative)
  6. Find the sum of the node value + left subtree sum + right subtree sum
  7. If this sum is greater than the already calculated maximum sum value replace it with the current sum
  8. Return the node value + the maximum of left and right tree sums to be used further up in the recursion call.
  9. Return the maximum path sum value after the recursive call completes.

Time complexity:

We traverse through every node once so time complexity is O(n)

Space complexity:

Recursion is invoked on every node so space complexity for the recursion stack is O(n)

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s