Find largest subtree sum in a tree

Last Updated : 18 Apr, 2023

Given a binary tree, task is to find subtree with maximum sum in tree.

Examples:

Input :       1
            /   \
           2      3
          / \    / \
         4   5  6   7
Output : 28
As all the tree elements are positive,
the largest subtree sum is equal to
sum of all tree elements.

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.

Recommended : Please try your approach first on IDE and then look at the solution.

Approach : Do post order traversal of the binary tree. At every node, find left subtree value and right subtree value recursively. The value of subtree rooted at current node is equal to sum of current node value, left node subtree sum and right node subtree sum. Compare current subtree sum with overall maximum subtree sum so far.

Implementation :

C++

// C++ program to find largest subtree
// sum in a given binary tree.
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a tree node.
struct Node {
    int key;
    Node *left, *right;
};
 
// Function to create new tree node.
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Helper function to find largest
// subtree sum recursively.
int findLargestSubtreeSumUtil(Node* root, int& ans)
{
    // If current node is null then
    // return 0 to parent node.
    if (root == NULL)     
        return 0;
     
    // Subtree sum rooted at current node.
    int currSum = root->key + 
      findLargestSubtreeSumUtil(root->left, ans)
      + findLargestSubtreeSumUtil(root->right, ans);
 
    // Update answer if current subtree
    // sum is greater than answer so far.
    ans = max(ans, currSum);
 
    // Return current subtree sum to
    // its parent node.
    return currSum;
}
 
// Function to find largest subtree sum.
int findLargestSubtreeSum(Node* root)
{
    // If tree does not exist, 
    // then answer is 0.
    if (root == NULL)     
        return 0;
     
    // Variable to store maximum subtree sum.
    int ans = INT_MIN;
 
    // Call to recursive function to
    // find maximum subtree sum.
    findLargestSubtreeSumUtil(root, ans);
 
    return ans;
}
 
// Driver function
int main()
{
    /*
               1
             /   \
            /     \
          -2       3
          / \     /  \
         /   \   /    \
        4     5 -6     2
    */
 
    Node* root = newNode(1);
    root->left = newNode(-2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(-6);
    root->right->right = newNode(2);
 
    cout << findLargestSubtreeSum(root);
    return 0;
}

Java

// Java program to find largest 
// subtree sum in a given binary tree. 
import java.util.*; 
class GFG
{
 
// Structure of a tree node. 
static class Node 
{ 
    int key; 
    Node left, right; 
} 
 
static class INT
{
    int v;
    INT(int a)
    {
        v = a;
    }
}
 
// Function to create new tree node. 
static Node newNode(int key) 
{ 
    Node temp = new Node(); 
    temp.key = key; 
    temp.left = temp.right = null; 
    return temp; 
} 
 
// Helper function to find largest 
// subtree sum recursively. 
static int findLargestSubtreeSumUtil(Node root, 
                                     INT ans) 
{ 
    // If current node is null then 
    // return 0 to parent node. 
    if (root == null)     
        return 0; 
     
    // Subtree sum rooted 
    // at current node. 
    int currSum = root.key + 
    findLargestSubtreeSumUtil(root.left, ans) + 
    findLargestSubtreeSumUtil(root.right, ans); 
 
    // Update answer if current subtree 
    // sum is greater than answer so far. 
    ans.v = Math.max(ans.v, currSum); 
 
    // Return current subtree 
    // sum to its parent node. 
    return currSum; 
} 
 
// Function to find 
// largest subtree sum. 
static int findLargestSubtreeSum(Node root) 
{ 
    // If tree does not exist, 
    // then answer is 0. 
    if (root == null)     
        return 0; 
     
    // Variable to store 
    // maximum subtree sum. 
    INT ans = new INT(-9999999); 
 
    // Call to recursive function 
    // to find maximum subtree sum. 
    findLargestSubtreeSumUtil(root, ans); 
 
    return ans.v; 
} 
 
// Driver Code 
public static void main(String args[])
{ 
    /* 
            1 
            / \ 
            /     \ 
        -2     3 
        / \     / \ 
        / \ / \ 
        4     5 -6     2 
    */
 
    Node root = newNode(1); 
    root.left = newNode(-2); 
    root.right = newNode(3); 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 
    root.right.left = newNode(-6); 
    root.right.right = newNode(2); 
 
    System.out.println(findLargestSubtreeSum(root)); 
} 
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to find largest subtree 
# sum in a given binary tree. 
 
# Function to create new tree node. 
class newNode:
    def __init__(self, key):
        self.key = key 
        self.left = self.right = None
 
# Helper function to find largest 
# subtree sum recursively. 
def findLargestSubtreeSumUtil(root, ans):
     
    # If current node is None then 
    # return 0 to parent node. 
    if (root == None): 
        return 0
     
    # Subtree sum rooted at current node. 
    currSum = (root.key +
               findLargestSubtreeSumUtil(root.left, ans) +
               findLargestSubtreeSumUtil(root.right, ans)) 
 
    # Update answer if current subtree 
    # sum is greater than answer so far. 
    ans[0] = max(ans[0], currSum) 
 
    # Return current subtree sum to 
    # its parent node. 
    return currSum
 
# Function to find largest subtree sum. 
def findLargestSubtreeSum(root):
     
    # If tree does not exist, 
    # then answer is 0. 
    if (root == None):     
        return 0
     
    # Variable to store maximum subtree sum. 
    ans = [-999999999999]
 
    # Call to recursive function to 
    # find maximum subtree sum. 
    findLargestSubtreeSumUtil(root, ans) 
 
    return ans[0]
 
# Driver Code 
if __name__ == '__main__':
     
    # 
    #         1 
    #         / \ 
    #     /     \ 
    #     -2     3 
    #     / \     / \ 
    #     / \ / \ 
    # 4     5 -6     2 
    root = newNode(1) 
    root.left = newNode(-2) 
    root.right = newNode(3) 
    root.left.left = newNode(4) 
    root.left.right = newNode(5) 
    root.right.left = newNode(-6) 
    root.right.right = newNode(2) 
 
    print(findLargestSubtreeSum(root))
 
# This code is contributed by PranchalK

C#

using System;
 
// C# program to find largest 
// subtree sum in a given binary tree. 
 
public class GFG
{
 
// Structure of a tree node. 
public class Node
{
    public int key;
    public Node left, right;
}
 
public class INT
{
    public int v;
    public INT(int a)
    {
        v = a;
    }
}
 
// Function to create new tree node. 
public static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return temp;
}
 
// Helper function to find largest 
// subtree sum recursively. 
public static int findLargestSubtreeSumUtil(Node root, INT ans)
{
    // If current node is null then 
    // return 0 to parent node. 
    if (root == null)
    {
        return 0;
    }
 
    // Subtree sum rooted 
    // at current node. 
    int currSum = root.key + findLargestSubtreeSumUtil(root.left, ans)
                        + findLargestSubtreeSumUtil(root.right, ans);
 
    // Update answer if current subtree 
    // sum is greater than answer so far. 
    ans.v = Math.Max(ans.v, currSum);
 
    // Return current subtree 
    // sum to its parent node. 
    return currSum;
}
 
// Function to find 
// largest subtree sum. 
public static int findLargestSubtreeSum(Node root)
{
    // If tree does not exist, 
    // then answer is 0. 
    if (root == null)
    {
        return 0;
    }
 
    // Variable to store 
    // maximum subtree sum. 
    INT ans = new INT(-9999999);
 
    // Call to recursive function 
    // to find maximum subtree sum. 
    findLargestSubtreeSumUtil(root, ans);
 
    return ans.v;
}
 
// Driver Code 
public static void Main(string[] args)
{
    /* 
            1 
            / \ 
            /     \ 
        -2     3 
        / \     / \ 
        / \ / \ 
        4     5 -6     2 
    */
 
    Node root = newNode(1);
    root.left = newNode(-2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right.left = newNode(-6);
    root.right.right = newNode(2);
 
    Console.WriteLine(findLargestSubtreeSum(root));
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
    // Javascript program to find largest 
    // subtree sum in a given binary tree. 
     
    // Structure of a tree node. 
    class Node
    {
        constructor(key) {
           this.left = null;
           this.right = null;
           this.key = key;
        }
    }
 
    let v;
 
    // Function to create new tree node. 
    function newNode(key) 
    { 
        let temp = new Node(key); 
        return temp; 
    } 
 
    // Helper function to find largest 
    // subtree sum recursively. 
    function findLargestSubtreeSumUtil(root) 
    { 
        // If current node is null then 
        // return 0 to parent node. 
        if (root == null)     
            return 0; 
 
        // Subtree sum rooted 
        // at current node. 
        let currSum = root.key + 
        findLargestSubtreeSumUtil(root.left) + 
        findLargestSubtreeSumUtil(root.right); 
 
        // Update answer if current subtree 
        // sum is greater than answer so far. 
        v = Math.max(v, currSum); 
 
        // Return current subtree 
        // sum to its parent node. 
        return currSum; 
    } 
 
    // Function to find 
    // largest subtree sum. 
    function findLargestSubtreeSum(root) 
    { 
        // If tree does not exist, 
        // then answer is 0. 
        if (root == null)     
            return 0; 
 
        // Variable to store 
        // maximum subtree sum. 
        v = -9999999; 
 
        // Call to recursive function 
        // to find maximum subtree sum. 
        findLargestSubtreeSumUtil(root); 
 
        return v; 
    } 
     
    /* 
            1 
            / \ 
            /     \ 
        -2     3 
        / \     / \ 
        / \ / \ 
        4     5 -6     2 
    */
   
    let root = newNode(1); 
    root.left = newNode(-2); 
    root.right = newNode(3); 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 
    root.right.left = newNode(-6); 
    root.right.right = newNode(2); 
   
    document.write(findLargestSubtreeSum(root));
 
// This code is contributed by divyesh072019.
</script>

Output

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes.
Auxiliary Space: O(n), function call stack size.

Using DFS approach:

The idea is to use depth first search recursively call for every subtree in left and right including root node and calculate for maximum sum for the same subtree.

Steps to solve the problem:

initialize ans variable with int min.
first check for the base condition.
calculate all the subtree with maximum sum in the left.
calculate all the subtree with maximum sum in the right.
store temporarily maximum value of left and right
update that temporarily stored value with maximum of sum of left , right and root node and that temp value.
update the ans variable to max(ans,tempmax).
return the sum.

Implementation of the approach:

C++

// C++ program to find largest subtree
// sum in a given binary tree.
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a tree node.
struct Node {
    int key;
    Node *left, *right;
};
 
// Function to create new tree node.
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
 
int ans = INT_MIN;
int dfs(Node* root)
{
    if (root == NULL)
        return 0;
    if (root->left == NULL and root->right == NULL)
        return root->key;
    // check for every subtree in left
    int sumleft = dfs(root->left);
    // check for every subtree in right
    int sumright = dfs(root->right);
    // sum of all the nodes in the subtree from root node
    int sumrootnode = sumleft + sumright + root->key;
    // temp max value of left and right subtree
    int tempmax = max(sumleft, sumright);
 
    tempmax = max(tempmax, sumrootnode);
    // update the answer from temp, ans
    ans = max(ans, tempmax);
 
    return sumrootnode;
}
int findLargestSubtreeSum(Node* root)
{
 
    // check for the base conditions
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return root->key;
    // function call of dfs
    int x = dfs(root);
    // return the final answer
    return ans;
}
 
// Driver function
int main()
{
    /*
               1
             /   \
            /     \
          -2       3
          / \     /  \
         /   \   /    \
        4     5 -6     2
    */
 
    Node* root = newNode(1);
    root->left = newNode(-2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(-6);
    root->right->right = newNode(2);
 
    cout << findLargestSubtreeSum(root);
    return 0;
}
//this code is contributed by Prateek Kumar Singh

Java

// Java program to find largest subtree
// sum in a given binary tree.
import java.io.*;
 
class GFG {
 
  // Structure of a tree node.
  static class Node {
    public int key;
    public Node left, right;
  }
 
  // Function to create new tree node.
  static Node newNode(int key)
  {
    Node temp = new Node();
    temp.key = key;
    temp.left = null;
    temp.right = null;
    return temp;
  }
 
  static int ans = Integer.MIN_VALUE;
  static int dfs(Node root)
  {
    if (root == null)
      return 0;
    if (root.left == null && root.right == null)
      return root.key;
    // check for every subtree in left
    int sumleft = dfs(root.left);
    // check for every subtree in right
    int sumright = dfs(root.right);
    // sum of all the nodes in the subtree from root
    // node
    int sumrootnode = sumleft + sumright + root.key;
    // temp max value of left and right subtree
    int tempmax = Math.max(sumleft, sumright);
 
    tempmax = Math.max(tempmax, sumrootnode);
    // update the answer from temp, ans
    ans = Math.max(ans, tempmax);
 
    return sumrootnode;
  }
 
  static int findLargestSubtreeSum(Node root)
  {
 
    // check for the base conditions
    if (root == null)
      return 0;
    if (root.left == null && root.right == null)
      return root.key;
    // function call of dfs
    int x = dfs(root);
    // return the final answer
    return ans;
  }
 
  public static void main(String[] args)
  {
    /*
                1
                / \
                /   \
            -2   3
            / \ / \
            / \ / \
            4 5 -6 2
        */
 
    Node root = newNode(1);
    root.left = newNode(-2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right.left = newNode(-6);
    root.right.right = newNode(2);
 
    System.out.println(findLargestSubtreeSum(root));
  }
}
 
// This code is contributed by lokesh.

Python3

# A tree node 
class Node: 
    def __init__(self, data): 
        self.data = data # Assign data 
        self.left = None # Initialize left child 
        self.right = None # Initialize right child 
 
# Find largest subtree sum in a given binary tree 
ans = float("-infinity") 
def findLargestSubtreeSum(root): 
    if root is None: 
        return 0
    if root.left is None and root.right is None: 
        return root.data 
       
    # Check for every subtree in left 
    sumleft = findLargestSubtreeSum(root.left) 
     
    # Check for every subtree in right 
    sumright = findLargestSubtreeSum(root.right) 
     
    # Sum of all the nodes in the subtree from root node 
    sumrootnode = sumleft + sumright + root.data 
     
    # Temp max value of left and right subtree 
    tempmax = max(sumleft, sumright) 
    tempmax = max(tempmax, sumrootnode) 
     
    # Update the answer from temp, ans 
    global ans 
    ans = max(ans, tempmax) 
    return sumrootnode 
 
# Driver Code 
if __name__ == '__main__': 
    root = Node(1) 
    root.left = Node(-2) 
    root.right = Node(3) 
    root.left.left = Node(4) 
    root.left.right = Node(5) 
    root.right.left = Node(-6) 
    root.right.right = Node(2) 
    findLargestSubtreeSum(root) 
    print(ans)

C#

// C# program to find largest subtree
// sum in a given binary tree.
 
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG {
    // Structure of a tree node.
    class Node {
        public int key; 
        public Node left, right;
    };
     
    // Function to create new tree node.
    static Node newNode(int key) 
    { 
        Node temp = new Node(); 
        temp.key = key; 
        temp.left = null;
        temp.right = null; 
        return temp; 
    }
     
 
    static int ans = Int32.MinValue;
    static int dfs(Node root)
    {
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return root.key;
        // check for every subtree in left
        int sumleft = dfs(root.left);
        // check for every subtree in right
        int sumright = dfs(root.right);
        // sum of all the nodes in the subtree from root node
        int sumrootnode = sumleft + sumright + root.key;
        // temp max value of left and right subtree
        int tempmax = Math.Max(sumleft, sumright);
     
        tempmax = Math.Max(tempmax, sumrootnode);
        // update the answer from temp, ans
        ans = Math.Max(ans, tempmax);
     
        return sumrootnode;
    }
    static int findLargestSubtreeSum(Node root)
    {
     
        // check for the base conditions
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return root.key;
        // function call of dfs
        int x = dfs(root);
        // return the final answer
        return ans;
    }
     
    // Driver function
    public static void Main()
    {
        /*
                   1
                 /   \
                /     \
              -2       3
              / \     /  \
             /   \   /    \
            4     5 -6     2
        */
     
        Node root = newNode(1);
        root.left = newNode(-2);
        root.right = newNode(3);
        root.left.left = newNode(4);
        root.left.right = newNode(5);
        root.right.left = newNode(-6);
        root.right.right = newNode(2);
     
        Console.Write(findLargestSubtreeSum(root));
    }
}

Javascript

// JavaScript Program to find largest subtree
// sum in a given binary tree
 
// Structure of a tree node
class Node{
    constructor(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
}
 
// Function to create new tree node
function newNode(key){
    let temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return temp;
}
 
let ans = Number.MIN_VALUE;
function dfs(root){
    if(root == null) return 0;
    if(root.left == null && root.right == null) return root.key;
     
    // check for every subtree in left
    let sumleft = dfs(root.left);
    // check for every subtree in right
    let sumright = dfs(root.right);
    // sum of all the nodes in the subtree from root node
    let sumrootnode = sumleft + sumright + root.key;
    // temp max value of left and right subtree
    let tempmax = Math.max(sumleft, sumright);
     
    tempmax = Math.max(tempmax, sumrootnode);
    // update the answer from temp, ans
    ans = Math.max(ans, tempmax);
  
    return sumrootnode;
}
 
function findLargestSubtreeSum(root){
    // check for the base conditions
    if (root == null)
        return 0;
    if (root.left == null && root.right == null)
        return root.key;
    // function call of dfs
    let x = dfs(root);
    // return the final answer
    return ans;
}
 
// Driver function
/*
           1
         /   \
        /     \
      -2       3
      / \     /  \
     /   \   /    \
    4     5 -6     2
*/
let root = newNode(1);
root.left = newNode(-2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.left = newNode(-6);
root.right.right = newNode(2);
 
document.write(findLargestSubtreeSum(root));
 
// This code is contributed by Yash Agarwal

Output

Time Complexity: O(n)
Auxiliary Space: O(h) where h is the height of the tree

this approach is contributed by Prateek Kumar Singh (pkrsingh025).

Using BFS approach :

The idea is to use breadth first search to store nodes (level wise) at each level in some container and then traverse these levels in reverse order from bottom level to top level and keep storing the subtree sum value rooted at nodes at each level. We can then reuse these values for upper levels.

subtree sum rooted at node = value of node + (subtree sum rooted at node->left) + (subtree sum rooted at node->right)

Steps to solve the problem:

First, check if tree is empty, then return 0.
Initialize ans variable with INT_MIN.
Create list of list of Nodes to store nodes at each level.
Also, create an map to store the sum of values for the subtree rooted at a particular node.
Now perform BFS by creating a queue and pushing the root in the queue.
Create a temporary list for storing nodes at current level
After traversing all nodes at current level, push this temporary list into our list of list of nodes.
Now, start traversing our levels list in reverse manner starting from last level towards the 1st level
For each level, traverse the nodes and find the subtree sum rooted at this node. We will use the already stored subtree sum values for nodes at below level
For each node traversed, Update the ans variable to maximum of ans and the value of subtree sum rooted at current node.
Return the ans.

Implementation of the approach:

C++

// C++ program to find largest subtree
// sum in a given binary tree.
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a tree node.
struct Node {
    int key;
    Node *left, *right;
};
 
// Function to create new tree node.
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
 
int findLargestSubtreeSum(Node* root)
{
    // Base case when tree is empty
    if (root == NULL)
        return 0;
 
    // Initialize answer to minimum value
    int ans = INT_MIN;
 
    // Queue for level order traversal
    queue<Node*> q;
 
    // Vector of Vector for storing nodes at a particular
    // level
    vector<vector<Node*> > levels;
 
    // Map for storing sum of subtree rooted at a particular
    // node
    unordered_map<Node*, int> subtreeSum;
 
    // Perform BFS
 
    // Push root to the queue
    q.push(root);
 
    while (!q.empty()) {
        // Get number of nodes in the queue
        int n = q.size();
 
        // Store nodes at current level
        vector<Node*> level;
        while (n--) {
            Node* node = q.front();
            // Push current node to current level vector
            level.push_back(node);
 
            // Add left & right child of node in the queue
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
 
            q.pop();
        }
 
        // add current level to levels vector
        levels.push_back(level);
    }
 
    // Traverse all levels from bottom most level to top
    // most level
    for (int i = levels.size() - 1; i >= 0; i--) {
        // Traverse all nodes in the current level
        for (auto e : levels[i]) {
            // add value of current node
            subtreeSum[e] = e->key;
 
            // If node has left child, add the subtree sum
            // of subtree rooted at left child
            if (e->left)
                subtreeSum[e] += subtreeSum[e->left];
 
            // If node has right child, add the subtree sum
            // of subtree rooted at right child
            if (e->right)
                subtreeSum[e] += subtreeSum[e->right];
 
            // update ans to maximum of ans and sum of
            // subtree rooted at current node
            ans = max(ans, subtreeSum[e]);
        }
    }
 
    // return the answer
    return ans;
}
 
// Driver function
int main()
{
    /*
                    1
                    / \
                    /     \
            -2     3
            / \     / \
            / \ / \
            4     5 -6     2
    */
 
    Node* root = newNode(1);
    root->left = newNode(-2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(-6);
    root->right->right = newNode(2);
 
    cout << findLargestSubtreeSum(root);
    return 0;
}
// this code is contributed by Piyush Garg (infinity4321cg)

Java

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;
 
class Node {
  int key;
  Node left, right;
 
  Node(int key)
  {
    this.key = key;
    left = right = null;
  }
}
 
public class Main {
 
  static int findLargestSubtreeSum(Node root)
  {
    // Base case when tree is empty
    if (root == null)
      return 0;
 
    // Initialize answer to minimum value
    int ans = Integer.MIN_VALUE;
 
    // Queue for level order traversal
    Queue<Node> q = new LinkedList<>();
 
    // Vector of Vector for storing nodes at a
    // particular level
    Vector<Vector<Node> > levels = new Vector<>();
 
    // Map for storing sum of subtree rooted at a
    // particular node
    HashMap<Node, Integer> subtreeSum = new HashMap<>();
 
    // Perform BFS
 
    // Push root to the queue
    q.add(root);
 
    while (!q.isEmpty()) {
      // Get number of nodes in the queue
      int n = q.size();
 
      // Store nodes at current level
      Vector<Node> level = new Vector<>();
      while (n-- > 0) {
        Node node = q.poll();
        // Push current node to current level vector
        level.add(node);
 
        // Add left & right child of node in the
        // queue
        if (node.left != null)
          q.add(node.left);
        if (node.right != null)
          q.add(node.right);
      }
 
      // add current level to levels vector
      levels.add(level);
    }
 
    // Traverse all levels from bottom most level to top
    // most level
    for (int i = levels.size() - 1; i >= 0; i--) {
      // Traverse all nodes in the current level
      for (Node e : levels.get(i)) {
        // add value of current node
        subtreeSum.put(e, e.key);
 
        // If node has left child, add the subtree
        // sum of subtree rooted at left child
        if (e.left != null)
          subtreeSum.put(
          e, subtreeSum.get(e)
          + subtreeSum.get(e.left));
 
        // If node has right child, add the subtree
        // sum of subtree rooted at right child
        if (e.right != null)
          subtreeSum.put(
          e, subtreeSum.get(e)
          + subtreeSum.get(e.right));
 
        // update ans to maximum of ans and sum of
        // subtree rooted at current node
        ans = Math.max(ans, subtreeSum.get(e));
      }
    }
 
    // return the answer
    return ans;
  }
 
  public static void main(String[] args)
  {
    /*
                        1
                        / \
                        /     \
                -2     3
                / \     / \
                / \ / \
                4     5 -6     2
        */
    Node root = new Node(1);
    root.left = new Node(-2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(-6);
    root.right.right = new Node(2);
 
    System.out.println(findLargestSubtreeSum(root));
  }
}

Javascript

// JavaScript program to find largest subtree
// sum in a given binary tree.
 
// Structure of a tree node.
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
 
function findLargestSubtreeSum(root) {
  // Base case when tree is empty
  if (root === null) return 0;
   
  // Initialize answer to minimum value
  let ans = -Infinity;
   
  // Queue for level order traversal
  const q = [];
   
  // array of array for storing nodes at a particular level
  const levels = [];
   
  // Map for storing sum of subtree rooted at a particular node
  const subtreeSum = new Map();
   
  // Perform BFS
  
  // Push root to the queue
  q.push(root);
  while (q.length > 0) {
      // Get number of nodes in the queue
    let n = q.length;
     
    // Store nodes at current level
    let level = [];
    while (n-- > 0) {
      const node = q.shift();
      // Push current node to current level vector
      level.push(node);
       
      // Add left & right child of node in the queue
      if (node.left !== null) q.push(node.left);
      if (node.right !== null) q.push(node.right);
    }
     
    // add current level to levels vector
    levels.push(level);
  }
   
  // Traverse all levels from bottom most level to top most level
  for (let i = levels.length - 1; i >= 0; i--) {
      // Traverse all nodes in the current level
    const level = levels[i];
    for (let j = 0; j < level.length; j++) {
      // add value of current node
      const e = level[j];
      subtreeSum.set(e, e.key);
       
      // If node has left child, add the subtree sum
      // of subtree rooted at left child
      if (e.left !== null) {
        subtreeSum.set(
          e,
          subtreeSum.get(e) + subtreeSum.get(e.left)
        );
      }
       
      // If node has right child, add the subtree sum
      // of subtree rooted at right child
      if (e.right !== null) {
        subtreeSum.set(
          e,
          subtreeSum.get(e) + subtreeSum.get(e.right)
        );
      }
       
      // update ans to maximum of ans and sum of
      // subtree rooted at current node
      ans = Math.max(ans, subtreeSum.get(e));
    }
  }
   
  // return the answer
  return ans;
}
 
/*
              1
              / \
             /   \
            /     \
           -2      3
          / \     / \
         /   \   /   \
        4     5 -6    2
*/
const root = new Node(1);
root.left = new Node(-2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(-6);
root.right.right = new Node(2);
 
console.log(findLargestSubtreeSum(root));
 
// This code is contributed by karthik

C#

// C# code addition for the above approach
 
using System;
using System.Collections.Generic;
 
// Structure of a tree node.
class Node {
    public int key;
    public Node left, right;
    public Node(int key)
    {
        this.key = key;
        left = right = null;
    }
}
 
public class GFG {
 
    static int findLargestSubtreeSum(Node root)
    {
        // Base case when tree is empty
        if (root == null)
            return 0;
 
        // Initialize answer to minimum value
        int ans = int.MinValue;
 
        // Queue for level order traversal
        Queue<Node> q = new Queue<Node>();
 
        // List of List for storing nodes at a particular
        // level
        List<List<Node> > levels = new List<List<Node> >();
 
        // Dictionary for storing sum of subtree rooted at a
        // particular node
        Dictionary<Node, int> subtreeSum
            = new Dictionary<Node, int>();
 
        // Push root to the queue
        q.Enqueue(root);
 
        // Perform BFS
        while (q.Count != 0) {
            // Get number of nodes in the queue
            int n = q.Count;
 
            // Store nodes at current level
            List<Node> level = new List<Node>();
            while (n-- > 0) {
                Node node = q.Dequeue();
                // Push current node to current level list
                level.Add(node);
 
                // Add left & right child of node in the
                // queue
                if (node.left != null)
                    q.Enqueue(node.left);
                if (node.right != null)
                    q.Enqueue(node.right);
            }
 
            // add current level to levels list
            levels.Add(level);
        }
 
        // Traverse all levels from bottom most level to top
        // most level
        for (int i = levels.Count - 1; i >= 0; i--) {
            // Traverse all nodes in the current level
            foreach(Node e in levels[i])
            {
                // add value of current node
                subtreeSum[e] = e.key;
 
                // If node has left child, add the subtree
                // sum of subtree rooted at left child
                if (e.left != null)
                    subtreeSum[e] += subtreeSum[e.left];
 
                // If node has right child, add the subtree
                // sum of subtree rooted at right child
                if (e.right != null)
                    subtreeSum[e] += subtreeSum[e.right];
 
                // update ans to maximum of ans and sum of
                // subtree rooted at current node
                ans = Math.Max(ans, subtreeSum[e]);
            }
        }
 
        // return the answer
        return ans;
    }
 
    static public void Main()
    {
 
        // Code
        /*
                                   1
                                  / \
                                 /     \
                               -2      3
                               / \     / \
                              /   \ /   \
                              4      5 -6     2
                */
        Node root = new Node(1);
        root.left = new Node(-2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(-6);
        root.right.right = new Node(2);
 
        Console.WriteLine(findLargestSubtreeSum(root));
    }
}
 
// This code is contributed by sankar.

Python3

from collections import deque
 
# Structure of a tree node.
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
# Function to create new tree node.
def newNode(key):
    temp = Node(key)
    return temp
 
def findLargestSubtreeSum(root):
    # Base case when tree is empty
    if root is None:
        return 0
 
    # Initialize answer to minimum value
    ans = float('-inf')
 
    # Queue for level order traversal
    q = deque()
 
    # List of Lists for storing nodes at a particular level
    levels = []
 
    # Map for storing sum of subtree rooted at a particular node
    subtreeSum = {}
 
    # Perform BFS
 
    # Push root to the queue
    q.append(root)
 
    while len(q) > 0:
        # Get number of nodes in the queue
        n = len(q)
 
        # Store nodes at current level
        level = []
        while n > 0:
            node = q.popleft()
            # Push current node to current level list
            level.append(node)
 
            # Add left & right child of node in the queue
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
 
            n -= 1
 
        # add current level to levels list
        levels.append(level)
 
    # Traverse all levels from bottom most level to top most level
    for i in range(len(levels) - 1, -1, -1):
        # Traverse all nodes in the current level
        for e in levels[i]:
            # add value of current node
            subtreeSum[e] = e.key
 
            # If node has left child, add the subtree sum
            # of subtree rooted at left child
            if e.left:
                subtreeSum[e] += subtreeSum[e.left]
 
            # If node has right child, add the subtree sum
            # of subtree rooted at right child
            if e.right:
                subtreeSum[e] += subtreeSum[e.right]
 
            # update ans to maximum of ans and sum of
            # subtree rooted at current node
            ans = max(ans, subtreeSum[e])
 
    # return the answer
    return ans
 
# Driver function
if __name__ == '__main__':
    """
                    1
                    / \
                    /     \
            -2     3
            / \     / \
            / \ / \
            4     5 -6     2
    """
    root = newNode(1)
    root.left = newNode(-2)
    root.right = newNode(3)
    root.left.left = newNode(4)
    root.left.right = newNode(5)
    root.right.left = newNode(-6)
    root.right.right = newNode(2)
 
    print(findLargestSubtreeSum(root))

Output

Time Complexity = Time complexity of BFS = O(N) where N is the number of nodes in the tree
Space Complexity = Space to store Nodes + Space to store sum values at each Node = O(N) + O(N) = O(N)

This approach is contributed by Piyush Garg (infinity4321cg)

nik1996

Improve

Previous Article

Check if a binary tree is subtree of another binary tree | Set 2

Maximum sum of nodes in Binary tree such that no two are adjacent

Similar Reads

Largest subtree sum for each vertex of given N-ary Tree

Given an N-array tree of N nodes, rooted at 1, with edges in the form {u, v}, and an array values[] consisting of N integers. Each vertex i has an integer value denoted by values[i]. The task is to find the largest Subtree Sum possible for each vertex i by adding its value to a non-empty subset of its child vertices. Examples: Input: Edges[][] = {{

Find the largest BST subtree in a given Binary Tree | Set 3

Largest BST in a Binary Tree | Set 3Method 3 (Shorter, Smarter and More Efficient) In this section, a different O(n) solution is discussed. This solution is simpler than the solutions discussed in Set-1 and Set-2 and works in O(n) time. In this method, we do not need to check explicitly if the binary tree is BST. A Tree is BST if the following is t

Find the largest Complete Subtree in a given Binary Tree

Given a Binary Tree, the task is to find the size of largest Complete sub-tree in the given Binary Tree. Complete Binary Tree - A Binary tree is Complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible. Note: All Perfect Binary Trees are Complete Binary tree but reve

Find the largest Perfect Subtree in a given Binary Tree

Given a Binary Tree, the task is to find the size of largest Perfect sub-tree in the given Binary Tree. Perfect Binary Tree - A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level. Examples: Input: 1 / \ 2 3 / \ / 4 5 6 Output: Size : 3 Inorder Traversal : 4 2 5 The following sub-tre

Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative

Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T. For Example: Input: Tree T - 1 / \ 2 3 / \ / \ 4 5 6 7 Tree S - 2 / \ 4 5 Output: YES Explanation: The above tree is the subtree of the tree T, Hence the output is YES Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each

Count of nodes in given N-ary tree such that their subtree is a Binary Tree

Given an N-ary tree root, the task is to find the count of nodes such that their subtree is a binary tree. Example: Input: Tree in the image below Output: 11Explanation: The nodes such that there subtree is a binary tree are {2, 8, 10, 6, 7, 3, 1, 9, 5, 11, 12}. Input: Tree in the image below Output: 9 Approach: The given problem can be solved by u

Check if a Binary tree is Subtree of another Binary tree | Set 3

Given two binary trees, check if the first tree is a subtree of the second one. A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree. Examples: Input: Tree-T Tree-S 1 3 / \ / 2

Check if a Binary Tree is subtree of another binary tree | Set 1

Given two binary trees, check if the first tree is a subtree of the second one. A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree. Examples: Input: Tree S 10 / \ 4 6 \ 30 Tr

Check if a binary tree is subtree of another binary tree | Set 2

Given two binary trees, check if the first tree is a subtree of the second one. A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.For example, in the following case, Tree1 i

Find largest subtree having identical left and right subtrees

Given a binary tree, find the largest subtree having identical left and right subtree. Expected complexity is O(n). For example, Input: 50 / \ 10 60 / \ / \ 5 20 70 70 / \ / \ 65 80 65 80 Output: Largest subtree is rooted at node 60 A simple solution is to consider every node, recursively check if left and right subtrees are identical using the app

Article Tags :

Practice Tags :

Tree