# Subtree with given sum in a Binary Tree

You are given a binary tree and a given sum. The task is to check if there exist a subtree whose sum of all nodes is equal to the given sum. Examples :

```// For above tree
Input : sum = 17
Output: "Yes"
// sum of all nodes of subtree {3, 5, 9} = 17

Input : sum = 11
Output: "No"
// no subtree with given sum exist
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to traverse tree in Postorder fashion because here we have to think bottom-up . First calculate the sum of left subtree then right subtree and check if sum_left + sum_right + cur_node = sum is satisfying the condition that means any subtree with given sum exist. Below is the recursive implementation of algorithm.

## C++

 `// C++ program to find if there is a subtree with ` `// given sum ` `#include ` `using` `namespace` `std; ` ` `  `/* A binary tree node has data, pointer to left child ` `   ``and a pointer to right child */` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node* left, *right; ` `}; ` ` `  `/* utility that allocates a new node with the ` `given data and NULL left and right pointers. */` `struct` `Node* newnode(``int` `data) ` `{ ` `    ``struct` `Node* node = ``new` `Node; ` `    ``node->data = data; ` `    ``node->left = node->right  = NULL; ` `    ``return` `(node); ` `} ` ` `  `// function to check if there exist any subtree with given sum ` `// cur_sum  --> sum of current subtree from ptr as root ` `// sum_left --> sum of left subtree from ptr as root ` `// sum_right --> sum of right subtree from ptr as root ` `bool` `sumSubtreeUtil(``struct` `Node *ptr, ``int` `*cur_sum, ``int` `sum) ` `{ ` `    ``// base condition ` `    ``if` `(ptr == NULL) ` `    ``{ ` `        ``*cur_sum = 0; ` `        ``return` `false``; ` `    ``} ` ` `  `    ``// Here first we go to left sub-tree, then right subtree ` `    ``// then first we calculate sum of all nodes of subtree ` `    ``// having ptr as root and assign it as cur_sum ` `    ``// cur_sum = sum_left + sum_right + ptr->data ` `    ``// after that we check if cur_sum == sum ` `    ``int` `sum_left = 0, sum_right = 0; ` `    ``return` `( sumSubtreeUtil(ptr->left, &sum_left, sum) || ` `             ``sumSubtreeUtil(ptr->right, &sum_right, sum) || ` `        ``((*cur_sum = sum_left + sum_right + ptr->data) == sum)); ` `} ` ` `  `// Wrapper over sumSubtreeUtil() ` `bool` `sumSubtree(``struct` `Node *root, ``int` `sum) ` `{ ` `    ``// Initialize sum of subtree with root ` `    ``int` `cur_sum = 0; ` ` `  `    ``return` `sumSubtreeUtil(root, &cur_sum, sum); ` `} ` ` `  `// driver program to run the case ` `int` `main() ` `{ ` `    ``struct` `Node *root = newnode(8); ` `    ``root->left    = newnode(5); ` `    ``root->right   = newnode(4); ` `    ``root->left->left = newnode(9); ` `    ``root->left->right = newnode(7); ` `    ``root->left->right->left = newnode(1); ` `    ``root->left->right->right = newnode(12); ` `    ``root->left->right->right->right = newnode(2); ` `    ``root->right->right = newnode(11); ` `    ``root->right->right->left = newnode(3); ` `    ``int` `sum = 22; ` ` `  `    ``if` `(sumSubtree(root, sum)) ` `        ``cout << ``"Yes"``; ` `    ``else` `        ``cout << ``"No"``; ` `    ``return` `0; ` `} `

## Java

 `// Java program to find if there  ` `// is a subtree with given sum  ` `import` `java.util.*;  ` `class` `GFG ` `{ ` ` `  `/* A binary tree node has data,  ` `pointer to left child and a ` `pointer to right child */` `static` `class` `Node  ` `{  ` `    ``int` `data;  ` `    ``Node left, right;  ` `} ` ` `  `static` `class` `INT ` `{ ` `    ``int` `v; ` `    ``INT(``int` `a) ` `    ``{ ` `        ``v = a; ` `    ``} ` `} ` ` `  `/* utility that allocates a new ` ` ``node with the given data and  ` ` ``null left and right pointers. */` `static` `Node newnode(``int` `data)  ` `{  ` `    ``Node node = ``new` `Node();  ` `    ``node.data = data;  ` `    ``node.left = node.right = ``null``;  ` `    ``return` `(node);  ` `}  ` ` `  `// function to check if there exist  ` `// any subtree with given sum  ` `// cur_sum -. sum of current subtree  ` `//            from ptr as root  ` `// sum_left -. sum of left subtree ` `//             from ptr as root  ` `// sum_right -. sum of right subtree ` `//              from ptr as root  ` `static` `boolean` `sumSubtreeUtil(Node ptr,  ` `                              ``INT cur_sum,  ` `                              ``int` `sum)  ` `{  ` `    ``// base condition  ` `    ``if` `(ptr == ``null``)  ` `    ``{  ` `        ``cur_sum = ``new` `INT(``0``);  ` `        ``return` `false``;  ` `    ``}  ` ` `  `    ``// Here first we go to left  ` `    ``// sub-tree, then right subtree  ` `    ``// then first we calculate sum  ` `    ``// of all nodes of subtree having  ` `    ``// ptr as root and assign it as  ` `    ``// cur_sum. (cur_sum = sum_left +  ` `    ``// sum_right + ptr.data) after that ` `    ``// we check if cur_sum == sum  ` `    ``INT sum_left = ``new` `INT(``0``),  ` `        ``sum_right = ``new` `INT(``0``);  ` `    ``return` `(sumSubtreeUtil(ptr.left, sum_left, sum) ||  ` `            ``sumSubtreeUtil(ptr.right, sum_right, sum) ||  ` `        ``((cur_sum.v = sum_left.v +  ` `                      ``sum_right.v + ptr.data) == sum));  ` `}  ` ` `  `// Wrapper over sumSubtreeUtil()  ` `static` `boolean` `sumSubtree(Node root, ``int` `sum)  ` `{  ` `    ``// Initialize sum of  ` `    ``// subtree with root  ` `    ``INT cur_sum = ``new` `INT( ``0``);  ` ` `  `    ``return` `sumSubtreeUtil(root, cur_sum, sum);  ` `}  ` ` `  `// Driver Code ` `public` `static` `void` `main(String args[]) ` `{  ` `    ``Node root = newnode(``8``);  ` `    ``root.left = newnode(``5``);  ` `    ``root.right = newnode(``4``);  ` `    ``root.left.left = newnode(``9``);  ` `    ``root.left.right = newnode(``7``);  ` `    ``root.left.right.left = newnode(``1``);  ` `    ``root.left.right.right = newnode(``12``);  ` `    ``root.left.right.right.right = newnode(``2``);  ` `    ``root.right.right = newnode(``11``);  ` `    ``root.right.right.left = newnode(``3``);  ` `    ``int` `sum = ``22``;  ` ` `  `    ``if` `(sumSubtree(root, sum))  ` `        ``System.out.println( ``"Yes"``);  ` `    ``else` `        ``System.out.println( ``"No"``);  ` `}  ` `} ` ` `  `// This code is contributed  ` `// by Arnab Kundu `

## Python3

 `# Python3 program to find if there is a  ` `# subtree with given sum  ` ` `  `# Binary Tree Node  ` `""" utility that allocates a newNode  ` `with the given key """` `class` `newnode:  ` ` `  `    ``# Construct to create a newNode  ` `    ``def` `__init__(``self``, key):  ` `        ``self``.data ``=` `key ` `        ``self``.left ``=` `None` `        ``self``.right ``=` `None` ` `  `# function to check if there exist any ` `# subtree with given sum  ` `# cur_sum -. sum of current subtree  ` `#            from ptr as root  ` `# sum_left -. sum of left subtree from  ` `#             ptr as root  ` `# sum_right -. sum of right subtree  ` `#              from ptr as root  ` `def` `sumSubtreeUtil(ptr,cur_sum,``sum``):  ` ` `  `    ``# base condition  ` `    ``if` `(ptr ``=``=` `None``): ` `        ``cur_sum[``0``] ``=` `0` `        ``return` `False` ` `  `    ``# Here first we go to left sub-tree,  ` `    ``# then right subtree then first we  ` `    ``# calculate sum of all nodes of subtree  ` `    ``# having ptr as root and assign it as cur_sum  ` `    ``# cur_sum = sum_left + sum_right + ptr.data  ` `    ``# after that we check if cur_sum == sum  ` `    ``sum_left, sum_right ``=` `[``0``], [``0``] ` `    ``x``=``sumSubtreeUtil(ptr.left, sum_left, ``sum``) ` `    ``y``=``sumSubtreeUtil(ptr.right, sum_right, ``sum``) ` `    ``cur_sum[``0``] ``=` `(sum_left[``0``] ``+`  `                  ``sum_right[``0``] ``+` `ptr.data) ` `    ``return` `((x ``or` `y)``or` `(cur_sum[``0``] ``=``=` `sum``)) ` ` `  `# Wrapper over sumSubtreeUtil()  ` `def` `sumSubtree(root, ``sum``):  ` ` `  `    ``# Initialize sum of subtree with root  ` `    ``cur_sum ``=` `[``0``]  ` ` `  `    ``return` `sumSubtreeUtil(root, cur_sum, ``sum``)  ` ` `  `# Driver Code  ` `if` `__name__ ``=``=` `'__main__'``: ` ` `  `    ``root ``=` `newnode(``8``)  ` `    ``root.left ``=` `newnode(``5``)  ` `    ``root.right ``=` `newnode(``4``)  ` `    ``root.left.left ``=` `newnode(``9``)  ` `    ``root.left.right ``=` `newnode(``7``)  ` `    ``root.left.right.left ``=` `newnode(``1``)  ` `    ``root.left.right.right ``=` `newnode(``12``)  ` `    ``root.left.right.right.right ``=` `newnode(``2``)  ` `    ``root.right.right ``=` `newnode(``11``)  ` `    ``root.right.right.left ``=` `newnode(``3``)  ` `    ``sum` `=` `22` ` `  `    ``if` `(sumSubtree(root, ``sum``)) : ` `        ``print``(``"Yes"` `) ` `    ``else``: ` `        ``print``(``"No"``) ` ` `  `# This code is contributed by ` `# Shubham Singh(SHUBHAMSINGH10) `

## C#

 `using` `System; ` ` `  `// C# program to find if there  ` `// is a subtree with given sum  ` `public` `class` `GFG ` `{ ` ` `  `/* A binary tree node has data,  ` `pointer to left child and a  ` `pointer to right child */` `public` `class` `Node ` `{ ` `    ``public` `int` `data; ` `    ``public` `Node left, right; ` `} ` ` `  `public` `class` `INT ` `{ ` `    ``public` `int` `v; ` `    ``public` `INT(``int` `a) ` `    ``{ ` `        ``v = a; ` `    ``} ` `} ` ` `  `/* utility that allocates a new  ` `node with the given data and  ` `null left and right pointers. */` `public` `static` `Node newnode(``int` `data) ` `{ ` `    ``Node node = ``new` `Node(); ` `    ``node.data = data; ` `    ``node.left = node.right = ``null``; ` `    ``return` `(node); ` `} ` ` `  `// function to check if there exist  ` `// any subtree with given sum  ` `// cur_sum -. sum of current subtree  ` `//         from ptr as root  ` `// sum_left -. sum of left subtree  ` `//             from ptr as root  ` `// sum_right -. sum of right subtree  ` `//             from ptr as root  ` `public` `static` `bool` `sumSubtreeUtil(Node ptr, INT cur_sum, ``int` `sum) ` `{ ` `    ``// base condition  ` `    ``if` `(ptr == ``null``) ` `    ``{ ` `        ``cur_sum = ``new` `INT(0); ` `        ``return` `false``; ` `    ``} ` ` `  `    ``// Here first we go to left  ` `    ``// sub-tree, then right subtree  ` `    ``// then first we calculate sum  ` `    ``// of all nodes of subtree having  ` `    ``// ptr as root and assign it as  ` `    ``// cur_sum. (cur_sum = sum_left +  ` `    ``// sum_right + ptr.data) after that  ` `    ``// we check if cur_sum == sum  ` `    ``INT sum_left = ``new` `INT(0), sum_right = ``new` `INT(0); ` `    ``return` `(sumSubtreeUtil(ptr.left, sum_left, sum)  ` `            ``|| sumSubtreeUtil(ptr.right, sum_right, sum)  ` `            ``|| ((cur_sum.v = sum_left.v + sum_right.v + ptr.data) == sum)); ` `} ` ` `  `// Wrapper over sumSubtreeUtil()  ` `public` `static` `bool` `sumSubtree(Node root, ``int` `sum) ` `{ ` `    ``// Initialize sum of  ` `    ``// subtree with root  ` `    ``INT cur_sum = ``new` `INT(0); ` ` `  `    ``return` `sumSubtreeUtil(root, cur_sum, sum); ` `} ` ` `  `// Driver Code  ` `public` `static` `void` `Main(``string``[] args) ` `{ ` `    ``Node root = newnode(8); ` `    ``root.left = newnode(5); ` `    ``root.right = newnode(4); ` `    ``root.left.left = newnode(9); ` `    ``root.left.right = newnode(7); ` `    ``root.left.right.left = newnode(1); ` `    ``root.left.right.right = newnode(12); ` `    ``root.left.right.right.right = newnode(2); ` `    ``root.right.right = newnode(11); ` `    ``root.right.right.left = newnode(3); ` `    ``int` `sum = 22; ` ` `  `    ``if` `(sumSubtree(root, sum)) ` `    ``{ ` `        ``Console.WriteLine(``"Yes"``); ` `    ``} ` `    ``else` `    ``{ ` `        ``Console.WriteLine(``"No"``); ` `    ``} ` `} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output:

```Yes
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

Tree Tree

code

load comments