Find largest subtree sum in a tree
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.
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> |
7
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 |
7
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)) |
7
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)
Contact Us