## Introduction

In this blog we will discuss a famous problem of binary trees. The problem is to count subtrees that sum up to a given value x only using a single recursive function. But wait before jumping directly to the problem let us first understand what exactly a binary tree is?

A binary tree is a data structure in which each parent node has no more than two children. A binary tree node is made up of three components:

- data
- pointer to left
- pointer to right

### Problem Statement

An binary tree with n nodes is provided. The goal of the problem is to count subtrees that sum up to a given value x only using a single recursive function.

Now, we need to find the subtree whose elements sum up to a given value. Letâ€™s have some examples to understand the concept of count subtrees that sum up to a given value more accurately.

### Sample Examples

**Example 1**

**Input:**

`x=1`

**Output: **

`No of subtrees with sum equal to x are: 2`

**Explanation:**

There are 2 subtrees with a sum of 1.

1st subtree is leaf node 1.

2nd subtree is {4, 2, -5}.

**Example 2**

**Input:**

`x=2`

**Output:**

`No of subtrees with sum equal to x are: 2`

**Explanation:**

There are 2 subtrees with a sum of 2.

1st is node leaf 2.

2nd is node leaf 6,1 and -5.

## Approach

Here is the approach to Count subtrees that sum up to a given value x only using a single recursive function.

In this method, we recursively calculate the weights of the left and right subtrees of the root node, and then we add those weights to the rootâ€™s weight. The count is increased if the sum is equal to x.

### Algorithm

Below is the algorithm to Count subtrees that sum up to a given value x only using a single recursive function

- If the root is NULL, then the sum is returned as 0.
- Compute the sum of nodes in the left subtree and in the right subtree.
- Set sum to sum=Left_subtree + Right_subtree + root->data.
- If the sum equals x, the count is increased.
- Return sum as sum = Left_subtree + root->data + Right subtree if temp!=root and not the start node.
- Finally, return the desired number of trees with node sums equal to x.

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
// Structure of a node of binary tree
struct Node
{
int data;
Node *left, *right;
};
// this function will get the new node
Node *getNode(int data)
{
// space Allocation
Node *newNode = (Node *)malloc(sizeof(Node));
// Put in the data
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// function to count subtrees that sum up to a given value x only using a single recursive function
int CountSubtree(Node *root, int x)
{
// variable to store the count of subtrees
static int count = 0;
static Node *ptr = root;
// l stores sum of the left subtree , right stores sum of the right sub tree
int l = 0, r = 0;
// edge case
if (root == NULL)
return 0;
l += CountSubtree(root->left, x);
r += CountSubtree(root->right, x);
// if we get the desired sum , increase counter variable
if (l + r + root->data == x)
count++;
if (ptr != root)
return l + root->data + r;
return count;
}
// Driver code to Count subtrees that sum up to a given value x only using a single recursive function
int main()
{
// constructing the tree
Node *root = getNode(2);
root->left = getNode(5);
root->right = getNode(8);
root->left->left = getNode(6);
root->left->right = getNode(3);
root->right->left = getNode(-5);
root->right->right = getNode(4);
int x = 14;
cout << "Count = "
<< CountSubtree(root, x);
return 0;
}
```

**Input:**

`x = 14`

**Output:**

`Count = 1`

**Algorithm Complexity**

**Time Complexity: O(N)**

Traversing every node of the tree once takes O(n) time; and since we are using inorder traversal, hence the time complexity to count subtrees that sum up to a given value is O(n).

**Space Complexity: O(1)**

If we ignore the stack space occupied by the recursion calls then the space complexity of this approach to count subtrees that sum up to a given value would be O(1).

Must Read __Recursion in Data Structure__