# Find largest subtree sum in a tree - GeeksforGeeks (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.`

(Video) Find largest subtree sum in a tree | GeeksforGeeks

`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.`

(Video) Largest subtree sum in a tree | Problem of The Day: 28/12/2022 | Yash Dwivedi

`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:

1. initialize ans variable with int min.
2. first check for the base condition.
3. calculate all the subtree with maximum sum in the left.
4. calculate all the subtree with maximum sum in the right.
5. store temporarily maximum value of left and right
6. update that temporarily stored value with maximum of sum of left , right and root node and that temp value.
7. update the ans variable to max(ans,tempmax).
8. 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;`

(Video) Largest subtree sum in a tree | Easiest Solution💥😃Problem of the Day #geeksforgeeks#leetcode

`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.`

(Video) Find Largest Subtree Sum in a Tree | GFG | Python | Love Babbar DSA Cracker Sheet

`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).

RecommendedSolve DSA problems on GfG Practice.Solve Problems

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? ›

Explanation: Minimum sum is 5 + 7 + 9 + 11 = 32 and maximum sum is 7 + 9 + 11 + 13 = 40.
...
Simple Approach:
1. Sort the array in ascending order.
2. Sum of the first N-1 elements in the array gives the minimum possible sum.
3. Sum of the last N-1 elements in the array gives the maximum possible sum.
Dec 21, 2022

What is subtree of all nodes in a tree? ›

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? ›

Note: Unique Sub-array sum means no other sub-array will have the same sum value.
...
Method 1 (Sorting Based):
1. Calculate the cumulative sum of an array.
2. Store all sub-array sum in vector.
3. Sort the vector.
4. Mark all duplicate sub-array sum to zero.
Aug 17, 2022

What is meant by maximum subarray sum problem? ›

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.

How do you find the height of a tree sum? ›

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.

## Videos

1. Find Largest Subtree Sum in a Binary Tree
(CppNuts)
2. Day 179 - Largest subtree sum in a tree | Tree | GFG POTD 28 Dec
(Sagar Malhotra)
3. Largest subtree sum in a tree || Day-123 Problem of the day || Tree || POTD
(Highlights Point)
4. Largest subtree sum in a tree || | Problem of the Day || gfg potd
(Rapid Coders)
5. Largest Subtree Sum in a Tree || Problem of the Day || Easy Solution || GFG || C++
(Mingle Tech)
6. Largest subtree sum in a tree || C++ || GFG Daily Problem
(CodeFreaks)
Top Articles
Latest Posts
Article information

Author: Trent Wehner

Last Updated: 04/25/2023

Views: 5328

Rating: 4.6 / 5 (56 voted)

Author information

Name: Trent Wehner

Birthday: 1993-03-14

Address: 872 Kevin Squares, New Codyville, AK 01785-0416

Phone: +18698800304764

Job: Senior Farming Developer

Hobby: Paintball, Calligraphy, Hunting, Flying disc, Lapidary, Rafting, Inline skating

Introduction: My name is Trent Wehner, I am a talented, brainy, zealous, light, funny, gleaming, attractive person who loves writing and wants to share my knowledge and understanding with you.