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.
The advantage of this code:
- The complete code is template base. So it will work with all the data types including class objects.
- Easy to specialize the template as per your requirement.
- The recursive mechanism has been used for traversing.
- 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;
}
More Articles of Yashaswi Raj:
| Name | Views | Likes |
|---|---|---|
| C++ boost::Variant | 1851 | 1 |
| C++ BOOST::ALGORITHM::IS_DIGIT( ) | 526 | 0 |
| C++ BOOST ::STRING ALGO::TO_UPPER_COPY( ) | 502 | 1 |
| C++::boost::variant::static_visitor | 1690 | 1 |
| C++::Boost::Variant::get( ) | 2412 | 1 |
| C++ PROGRAM TO FIND MAX SUBTREE SUM IN A TREE | 404 | 1 |
| C++ BOOST::ALGORITHM::STRING COMPARE | 1604 | 1 |
| C++::Boost::Variant::Apply_visitor( ) | 2266 | 1 |
| C++ BOOST ::STRING ALGO::ERASE( ) | 780 | 1 |
| C++ BOOST::ALGORITHM::REPLACE | 1221 | 0 |
| C++ BOOST::ALGORITHM::FIND FUNCTION | 819 | 1 |
| C++ Boost::variant::variant | 390 | 2 |
| GSD | 331 | 7 |
| C++ BOOST::ALGORITHM::TRIM | 1106 | 1 |
Comments
Yashaswi
25-Oct-2019 05:31:12 AM