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
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.
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
7
Time Complexity: O(n)
Auxiliary Space: O(1)
this approach is contributed by Prateek Kumar Singh (pkrsingh025).
My Personal Notes arrow_drop_up
FAQs
How do you find the largest subtree? ›
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.
What is subtree sum of a tree? ›The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). Constraints: The number of nodes in the tree is in the range [1, 104] .
What is the largest BST subtree in a tree? ›The largest BST node is 30 and the size is 1. 30 & 40- They are also leaf nodes, therefore, the data members follow the same rule as 12. 37- It is a BST because the left subtree node, 37 is lesser in value and right subtree node, 40 is greater in value than it.
What is the largest BST subtree in a given binary tree if entire subtree has to be taken? ›EXPLANATION: Since the entire Binary Tree is the BST. Hence, the largest BST Subtree is of size 6.
How do you find the maximum sum of a binary tree? ›Given the root of a binary tree, the level of its root is 1 , the level of its children is 2 , and so on. Return the smallest level x such that the sum of all the values of nodes at level x is maximal. Example 1: Input: root = [1,7,0,7,-8,null,null] Output: 2 Explanation: Level 1 sum = 1.
How do you find the number of subtrees in a tree? ›The number of possible subtrees for a given node is the number of possible subtrees that can be built from all children multiplied with each other. With cardinality |N| = |A| * |B| * |C| + 1 . Now for the root of the tree we need to eliminate two cases: the empty subtree.
Is a subtree in the larger tree? ›A sub-tree is a tree itself that is the subset of a bigger binary tree. A subtree of a node means that it is the child of that node.
What is sub sum? ›subsum (plural subsums) (mathematics) The sum of a subset of values.
What is the maximum average value of a subtree? ›The sum of values of all the nodes in the subtree / Total number of nodes in the subtree. Explanation: Average value of subtree with node(15) = (15 + 8 + 6) / 3 = 9.66667 maximum average of subtree values.
What is the largest BST subtree C++? ›Largest BST in a Binary Tree in C++
'3' is the subtree's size, so the return value is the subtree's size. Subtrees with nodes whose length is less than the length of their parent nodes have up to three size BST nodes. For every node x, a binary tree is BST if the following points are valid.
How do you find the largest element in BST? ›
To find Kth largest element in a Binary search tree, the simplest logic is to do reverse inorder traversal and while doing reverse inorder traversal simply keep a count of number of Nodes visited. When the count becomes equal to k, we stop the traversal and print the data.
What is the number of subtrees in a tree with 9 nodes? ›Together with 1 empty set that gives us 9 + 8 + 3 + 1 = 21.
How do I calculate subtree size? ›Calculate subtree size at every node. Then, score of a node = (product of size of subtree from every child) * (size of FULL tree - size of subtree at node).
What is a greater sum tree? ›What is a greater sum tree: Greater sum tree is a tree in which every node contains the sum of all the nodes which are greater than the node. see the example below. Approach: The naive approach will be for every node, traverse the tree and find out all the nodes which are greater and update the node.
What is the largest BST subtree coding ninjas? ›You are supposed to return the largest subtree sum in the given Binary Tree. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). Input Format : The first line contains an integer 'T' which denotes the number of test cases.
What is the maximum sum subset? ›Maximum subset sum such that no two elements in set have same digit in them. Given an array of N elements. Find the subset of elements which has maximum sum such that no two elements in the subset has common digit present in them. Maximum Sum Subset will be = {45, 223} .
What is maximum sum path in a tree? ›The idea is that, for each node, find two paths(the paths starting from that node and reaching to any depth) with the maximum path sum. The maximum result for that node will be equal to the sum of those two paths with the node. The maximum among all the nodes is the maximum path sum of the tree.
How do you find the sum of maximum and minimum? ›...
Simple Approach:
- Sort the array in ascending order.
- Sum of the first N-1 elements in the array gives the minimum possible sum.
- Sum of the last N-1 elements in the array gives the maximum possible sum.
Subtree. In the tree in data structures, each child from a node shapes a sub-tree recursively and every child in the tree will form a sub-tree on its parent node. Now you will look into the types of trees in data structures.
What is a subtree in binary tree? ›A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
What is number of subtrees of a node in a given tree called as? ›
Degree of a Node : The degree of a node of a tree is the number of subtrees having this node as a root. In other words, the degree is the number of descendants of a node. If the degree is zero, it is called a terminal or leaf node of a tree.
How do you find the subtree of a binary tree? ›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.
How many subtrees are in a binary tree? ›Structurally, a complete binary tree consists of either a single node (a leaf) or a root node with a left and right subtree, each of which is itself either a leaf or a root node with two subtrees.
Is larger than all the numbers in the sub tree below it what is this method called? ›Explanation:-A Sorting technique which uses the binary tree concept such that label of any node is larger than all the labels in the sub trees is called Heap sort because heap sort works on a complete binary tree with the property that the value at any node N of the tree should be greater than or equal to the value at ...
How do you find the sum of each Subarray? ›...
Method 1 (Sorting Based):
- Calculate the cumulative sum of an array.
- Store all sub-array sum in vector.
- Sort the vector.
- Mark all duplicate sub-array sum to zero.
- Calculate and return totalSum.
In computer science, the maximum sum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1...n] of numbers. Formally, the task is to find indices and with , such that the sum.
Is subtotal the same as sum? ›The SUM function will include filtered rows in its calculation while the SUBTOTAL function will exclude filtered data by only using the rows that remain visible after filters are applied.
What is the maximum number of children a node can have in binary tree *? ›A binary tree has a special condition that each node can have two children at maximum. “In computer science, a binary tree is a tree data structure in which each node has at the most two children, which are referred to as the left child and the right child.”
What is the maximum degree of a node in a binary tree? ›A non-leaf node is often called a branch node. The degree of a tree is the maximum degree of a node in the tree. A binary tree is degree 2.
How do you find the minimum and maximum number of nodes in a binary tree? ›The maximum number of nodes in a complete binary tree is 2h+1 -1. The minimum number of nodes in a complete binary tree is 2h. The minimum height of a complete binary tree is log2(n+1) – 1.
What is the max size of binary search tree? ›
Both the Binary Search Trees have a height of 2. Hence, the maximum height is 2.
What is the size of a binary tree in C++? ›Size of a binary tree is the total number of nodes in the tree. The number of nodes along the longest/shortest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0.
How do you find the largest element in a stack? ›Below is the step by step algorithm to do this:
Compare the element with the top element of the track stack, if the current element is greater than the top of trackStack then push the current element to trackStack otherwise push the top element of trackStack again into it.
sum-of-heights Σh = n – h – 1. We explain the observation with a small inductive proof. The induction is on h, the height of the tree. We first show that the observation holds for h = 0 (the inductive basis).
How do you know which element is the largest? ›To find the largest element from the array, a simple way is to arrange the elements in ascending order. After sorting, the first element will represent the smallest element, the next element will be the second smallest, and going on, the last element will be the largest element of the array.
How do you find the largest element in a tree? ›In Binary Search Tree, we can find maximum by traversing right pointers until we reach the rightmost node. But in Binary Tree, we must visit every node to figure out maximum. So the idea is to traverse the given tree and for every node return maximum of 3 values.
What is subtree size? ›The set of all nodes underneath a particular node x is called the subtree rooted at x. The size of a tree is the number of nodes; a leaf by itself has size 1. The height of a tree is the length of the longest path; 0 for a leaf, at least one in any larger tree.
Which of the following is logic for calculating size of a tree? ›Size of a tree = Size of left subtree + 1 + Size of right subtree.
How do you find the maximum number of nodes in a tree? ›2) Maximum number of nodes in a binary tree of height 'h' is 2h – 1. Here height of a tree is maximum number of nodes on root to leaf path. Height of a tree with single node is considered as 1. This result can be derived from point 2 above.
What is the number of subtrees of a node? ›The number of subtrees of a node is called its degree. For example, node A is of degree three, while node E is of degree two. The maximum degree of all nodes is called the degree of the tree.