Binary Trees: Find largest subtree sum in a tree

Problem Statement:

Given a binary tree, you need to find the subtree with maximum sum in tree.

Example

Input :

              1
            /    \
          -2      3
          / \    /  \
         4   5  -6   2

Output : 7

Subtree with largest sum is :


                              -2
                             /  \ 
                            4    5

Also, entire tree sum is also 7.

Solution

We need to do post order traversal of the binary tree.

You need to find left sub tree value and right sub tree value recursively.

Then check if the sum of the nodes of current node is greater than sum of left or right subtree.

Then compare the current subtree sum with overall maximum subtree sum so far.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <unordered_map> 

using namespace std;

struct node 
{ 
      int data; 
      node *left; 
      node *right; 

    node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
}; 
  
 
int find_largest_subtree_sum_util(node* root, int& ans)
{

    if (root == NULL)     
        return 0;
      
    int currSum = root->data + 
      find_largest_subtree_sum_util(root->left, ans)
      + find_largest_subtree_sum_util(root->right, ans);
  
    ans = max(ans, currSum);
  
    return currSum;
}
  
int find_largest_subtree_sum(node* root)
{

    if (root == NULL)     
        return 0;
      
    int ans = INT_MIN;
  
    find_largest_subtree_sum_util(root, ans);
  
    return ans;
}
 
int main()
{
    node* root = NULL;
    root = new node(1);
    root->left = new node(2);
    root->right = new node(3);
    root->left->left = new node(4);
    root->right->left = new node(2);
    root->right->left->left = new node(4);
    root->right->right = new node(4);

    cout<<"Maximum subtree sum is "<< find_largest_subtree_sum(root)<<endl;

    return 0;
}

Output:

Maximum subtree sum is 20

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *