# 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

Tree Tree