Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Algorithm Complexity
3.
Frequently asked questions
3.1.
Why is the recursion tree method used?
3.2.
How do you figure out the time and space complexity of a recursive function?
3.3.
What is recursion in programming?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count subtrees that sum up to a given value x only using a single recursive function

Author Prerna Tiwari
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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

  1. If the root is NULL, then the sum is returned as 0.
  2. Compute the sum of nodes in the left subtree and in the right subtree.
  3. Set sum to sum=Left_subtree + Right_subtree + root->data.
  4. If the sum equals x, the count is increased.
  5. Return sum as sum = Left_subtree + root->data + Right subtree if temp!=root and not the start node.
  6. 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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently asked questions

Why is the recursion tree method used?

A Recursion Tree is used to generate a close guess, which can be verified by the Substitution Method.

How do you figure out the time and space complexity of a recursive function?

The space complexity of a recursive algorithm is proportional to the maximum depth of the recursion tree generated.

What is recursion in programming?

Recursion is a technique of invoking a function by itself one or more times until a specified condition is satisfied.

Conclusion

In this article, we have discussed the problem “Count subtrees that sum up to a given value x only using a single recursive function.” We started with introducing the binary tree, problem statement, example, approach, and implementation of the problem in C++, and finally concluded with the time and space complexity of the algorithm.

We hope you have gained a better understanding of the solution to this problem, and now it is your responsibility to solve it and try some new and different approaches. 

If you want to practice problems on binary trees, you can refer to these links:

  1. BST to sorted DLL
  2. Binary Tree Pruning
  3. Left View Of Binary Tree
  4. Symmetric Tree
  5. Reverse a Stack using Recursion
     

You can also refer to our Guided Path on Coding Ninjas Studio to learn about Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more! Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Coding.

Previous article
Maximum average of subtree values in a given Binary Tree
Next article
Count Number of Nodes
Live masterclass