Q:

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

mahmoud2506
Save to bookmark
|
2022-05-01
|
  271 
0

Maximum path sum in a binary tree

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.

Example with explanation:

    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).
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | Recursion
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given an array of n integers. Find the minimum num... >>
<< You are given N eggs, and building with K floors f...