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