Home » Interview coding problems/challenges

Maximum path sum in a binary tree

Maximum path sum in a binary tree: You need to return the maximum sum of nodes in a binary tree. The nodes may contain negative values. The max sum path problem has been asked in Directi, Amazon, and other companies.
Submitted by Divyansh Jaipuriyar, on April 30, 2020

Problem statement

Given a binary Tree find the maximum path sum. The path may start and end at any node in the tree.

Input

The first and the only argument contains a pointer to the root of binary tree.

Output

Return an integer representing the maximum sum path.

Explanation with example

    Input: 
      6
    /  \
   3    9


    Output: 
    18
    (3->6->9), since all are positive integer, 
    we should consider all nodes sum.

    Input: 
    -14
    /  \
  -26  -36


    Output: 
    -14
    The path sum is maximum at node (-14).

Solution Approach

we will use the following concept.

For each node there can be four ways that the maximum sum path goes through the node:

1. Node only.
2. Maximum sum path through Left Child + Node.
3. Maximum sum path through Right Child + Node.
4. Maximum sum through Left Child + Node + Max path through Right Child.

we will initialize the resultant maximum sum variable res with INT_MIN, then we will use an ampersand operator for that variable and keep changing it with the following cases: we keep track of four paths and pick up the max one in the end. An important thing to note is, the root of every subtree need to return maximum path sum such that at most one child of root is involved. This is needed for the parent function call.

In the below code, this sum is stored in 'temp' and returned by the recursive function.

Standard Node:

stuct Node
{
	int data;
	Node *left,*right;
	Node(int data)
	{
		this->data=data;
		left=NULL;
		right=NULL;
	}
};

We will use the above node for further operation.

Pseudo Code

maxsum(Node *root,&res){
	// if root is NULL then simply return 0.
	if(root==NULL)
		return 0

	// declare temporary variables.
	int temp,int lh,int rh,ans;   

	// call recursive for left half of the node.
	lh=maxsum(root->left,res)     
	
	// call recursive for right half of the node.
	rh=maxsum(root->right,res)    
	
	// temp variable will store sum of current node 
	// value either by. 
	temp=max(max(lh,rh)+root->data,root->data) 
	
	//considering its own value or by combining the 
	// maximum value from left half or right 
	// half of the node.
	// ans will store the maximum sum node value 
	// considering if the current node
	// is the maximum value by checking left half 
	// and right half and node value sum.
	ans=max(temp,lh+rh+root->data)     
	
	res=max(res,ans)    // res will store maximum sum.
	
	return temp;	    // return temp sum value.
}		

Time Complexity for above code is O(n).

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Node //node declaration
    {
    int data;
    Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

int maxsum(Node* root, int& res) // maxsum function
{
    if (root == NULL) // if root==NULL return 0
        return 0;
    int lh, rh, temp, ans;
    lh = maxsum(root->left, res); //left half recursive call
    rh = maxsum(root->right, res); //right half recursive call
    temp = max(root->data, max(lh, rh) + root->data); // temp sum
    ans = max(temp, lh + rh + root->data);
    res = max(res, ans);
    return temp; //return temp sum
}

int maxsumutility(Node* root) // utility function to give max sum
{
    int res = INT_MIN; //initialise res as minimum value
    maxsum(root, res);
    return res;
}

int main()
{
    Node* root = new Node(10);
    root->left = new Node(12);
    root->right = new Node(-6);
    root->left->left = new Node(14);
    root->left->right = new Node(25);
    root->right->left = new Node(-9);
    root->right->right = new Node(15);
    root->left->left->left = new Node(-2);
    root->left->left->right = new Node(3);

    cout << "Maximum sum: ";
    int finalres = maxsumutility(root);
    cout << finalres << "\n";
    return 0;
}

Output

Maximum sum: 56