### C++ PROGRAM TO FIND MAX SUBTREE SUM IN A TREE

PROBLEM : GIVEN A BINARY TREE , FIND THE MAXIMUM SUM OF A SUBTREE . THE SUBTREE CAN BE THE ORIGINAL
TREE ALSO.

PROBLEM DESCRIPTION:  WE ARE GIVEN A TREE AND WE HAVE TO FIND THE MAXIMUM OF ALL THE SUBTREE SUM.
THE SUBTREE SUM IN AT A NODE IS EQUAL TO ITS CURRENT NODE VALUE  , LEFT SUBTREE                                                        VALUE AND RIGHT SUBTREE VALUE. THE SUBTREE VALUE OF LEAF NODE IS ITS OWN                                                                  VALUE . WHILE THAT OF THE ROOT NODE IS SAME AS TOTAL SUM OF ALL NODES IN TREE.

SOLUTION APPROACH :    WE DO RECURSIVE POST-ORDER TRAVERSAL OF THE TREE I.E  LEFT-RIGHT-ROOT . WE FIRST REACH THE LEFT MOST LEAF NODE  ,THEN ITS RIGHT NODE AND RECURSIVELY  GO TO THE ROOT NODE AFTER TRAVERSING ALL THE NODES IN THE SPECIFIED ORDER. WE INITIALLY MAKE THE MAXIMUM SUB_TREESUM  = INT_MIN.
AS WE TRAVERSE THE NODES WE COMPARE THE CURRENT VALUE OF THE SUBTREE ROOTED AT THAT NODE WITH THE MAXIMUM SUBTREE SUM . IF THE CURRENT SUBTREE SUM IS GREATER THAN THE MAXIMUM SUBTREE SUM THEN WE MAKE THE MAXIMUM SUBTREE SUM EQUAL TO CURRENT SUBTREE SUM AND  IN THIS WAY TRAVERSE TILL THE ROOT NODE TO FIND THE MAXIMUM SUBTREE SUM.

1. The complete code is template base. So it will work with all the data types including class objects.
2. Easy to specialize the template as per your requirement.
3. The recursive mechanism has been used for traversing.
4. Structure of the node is also templated.
5. TIME COMPLEXITY IS O(N) IN ALL CASES.

STEP 1:
MAX_SUBTREESUM=INT_MIN
CURRENT SUBTREESUM= 4
SINCE CURRENT SUBTREE SUM > MAX_SUBTREESUM
THEREFORE  MAX_SUBTREESUM =4

STEP 2:
MAX_SUBTREESUM=4
CURRENT SUBTREESUM= 5
SINCE CURRENT SUBTREE SUM > MAX_SUBTREESUM
THEREFORE  MAX_SUBTREESUM =5

STEP 3:
MAX_SUBTREESUM=5
CURRENT SUBTREESUM= 7
SINCE CURRENT SUBTREE SUM > MAX_SUBTREESUM
THEREFORE  MAX_SUBTREESUM =7

STEP 4:
MAX_SUBTREESUM=7
CURRENT SUBTREESUM= -6
SINCE CURRENT SUBTREE SUM < MAX_SUBTREESUM
THEREFORE  MAX_SUBTREESUM =7

STEP 5:
MAX_SUBTREESUM=7
CURRENT SUBTREESUM= 2
SINCE CURRENT SUBTREE SUM < MAX_SUBTREESUM
THEREFORE  MAX_SUBTREESUM =7

STEP 6:
MAX_SUBTREESUM=7
CURRENT SUBTREESUM= -1
SINCE CURRENT SUBTREE SUM < MAX_SUBTREESUM
THEREFORE  MAX_SUBTREESUM =7

STEP 7:
MAX_SUBTREESUM=7
CURRENT SUBTREESUM= 7
SINCE CURRENT SUBTREE SUM = MAX_SUBTREESUM
THEREFORE  MAX_SUBTREESUM =7

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

template<typename T>
struct Node {
T key;
Node *left, *right;
};

template<typename T>
Node<T>* newNode(T key)
Node<T>* temp = new Node<T>;
temp->key = key;
temp->left = temp->right = NULL;
return temp;

template<typename T>
T findLargestSubtreeSumUtil(Node<T>* root, T& ans)

if (root == NULL)
return 0;

T currSum = root->key +
findLargestSubtreeSumUtil<T>(root->left, ans)
+ findLargestSubtreeSumUtil<T>(root->right, ans);

ans = max(ans, currSum);

return currSum;

template<typename T>
T findLargestSubtreeSum(Node<T>* root)
if (root == NULL)
return 0;

T ans = INT_MIN;

findLargestSubtreeSumUtil<T>(root, ans);

return ans;

int main()

Node<int>* root = newNode<int>(1);
root->left = newNode<int>(-2);
root->right = newNode<int>(3);
root->left->left = newNode<int>(4);
root->left->right = newNode<int>(5);
root->right->left = newNode<int>(-6);
root->right->right = newNode<int>(2);

cout << findLargestSubtreeSum<int>(root);

return 0;