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 Example 
2.
Recursive Approach 
2.1.
Steps Of Algorithm 
3.
Implementation in C++
4.
Implementation in Java 
4.1.
Complexity analysis
5.
Frequently Asked Questions
5.1.
What exactly is a Red-Black tree data structure?
5.2.
How do you determine whether a binary tree is a subtree of another binary tree?
5.3.
What are tree traversal algorithms?
6.
Conclusion
Last Updated: Mar 27, 2024

Subtree with given sum in a Binary Tree

Author Shivani Singh
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Here in this blog, we are asked to see various approaches to find a subtree with a given sum in a binary tree. We already are familiar with the concept of the subtree and binary tree and also its features and implementations. So, let's dig a little deeper into this blog.

Source: binary tree

Problem Statement 

In this problem, we are provided a binary tree and also a sum and we are asked to find if there exists a subtree whose sum of all the nodes is equal to the given sum. If that subtree exists, we have to print yes else print no. Let us understand the problem statement with the help of an example. We need to keep in mind that for the binary tree If the level of the root is zero, a binary tree can have a maximum of 2l nodes at level l.

When each binary tree node has one or two children, the number of leaf nodes (nodes with no children) is one greater than the number of nodes with two children.

Sample Example 

 

Explanation: Suppose our given sum is 6. So we have to find if there is any subtree in this binary tree that has the sum of its node 6. If we look closely, we will see that there exists one subtree with a sum 6. The right child of root node here is 3,the children of 3 are 2 and 1. So the sum of three nodes = 6, which is equal to our target sum. So we can say that, yes, a subtree exists.

Here the approach we will be using is the sum of the current subtree= sum of the left subtree + sum of right subtree + value of current node.

Here, the sum of the current subtree = 3 + 2 + 1 = 6, which is equal to the sum.

From the above diagram, we can clearly understand the problem statement and the approach we will use to solve it. 

Recursive Approach 

This approach is very simple to implement and straightforward. Recursion is commonly used to solve tree questions. We use recursion to solve this problem as well.

As with most Binary tree problems, we start with the traversal. In this case, traversing the tree in post-order makes sense. While post traversing, we will keep in mind that sum of the current subtree = the sum of the left subtree + the sum of the right subtree + the value of the current node.

 

Let us see its algorithm. 

Steps Of Algorithm 

Step 1: If the root is null, return false.

Step 2: We will calculate the sum of the left subtree. 

Step 3: Then we will calculate the sum of the right subtree. 

Step 4: In the end, we will check for the condition sum_left_tree + sum_right_tree + current_node = given_sum.

Step 5: If this condition exists, that means the subtree exists with the given sum and we will simply print yes. 

Let us see the implementation of this approach in the next section of this blog.

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

Implementation in C++

#include<bits/stdc++.h>
using namespace std;
struct Node
{ 
     int data;
     struct Node* left, *right;
};
struct Node* newnode(int data)
{
     struct Node* node = new Node;
     node->data = data;
     node->left = node->right = NULL;
     return (node);
}
/* 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 subTree_exists(struct Node *ptr, int *cur_node_sum, int sum)
{
        if (ptr == NULL)  // base condition
        {
                *cur_node_sum = 0;
                return false;
        }
        int sum_left_tree = 0, sum_right_tree = 0;
        return ( subTree_exists(ptr->left, &sum_left_tree, sum) ||
        subTree_exists(ptr->right, &sum_right_tree, sum) ||
        ((*cur_node_sum = sum_left_tree + sum_right_tree + ptr->data) == sum));
}
bool sumSubtree(struct Node *root, int sum)
{
       /* Initialize sum of subtree with root */
       int cur_sum = 0;
       return subTree_exists(root, &cur_sum, sum);
}
int main()
{
       struct Node *root = newnode(5);
       root->left = newnode(4);
       root->right = newnode(3);
       root->left->left = newnode(3);
       root->left->right = newnode(2);
       root->right->left = newnode(2);
       root->right->right = newnode(1);
       
       int sum = 6;
       if (sumSubtree(root, sum))
                cout << "Subtree with the given sum " << sum << " exists";
       else
                cout << "Subtree with the given sum does not exist";
       return 0;
}

 

Output:

Subtree with the given sum 6 exists

Implementation in Java 

import java.util.*;
public class binaryTree
{
     static class Node
     {
         int data;
         Node left, right;
     }
     static class INT
     {
         int v;
         INT(int a)
         {
             v = a;
         }
     }
     static Node newnode(int data)
     {
         Node node = new Node();
         node.data = data;
         node.left = node.right = null;
         return (node);
     }
     // 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 subTree_exists(Node ptr,
         INT cur_node_sum,
         int sum)
     {
         if (ptr == null)  // base condition
         {
             cur_node_sum = new INT(0);
             return false;
         }
         INT sum_left_tree = new INT(0),
             sum_right_tree = new INT(0);
         return (subTree_exists(ptr.left, sum_left_tree, sum) ||
             subTree_exists(ptr.right, sum_right_tree, sum) ||
             ((cur_node_sum.v = sum_left_tree.v +
                 sum_right_tree.v + ptr.data) == sum));
     }
     static boolean sumSubtree(Node root, int sum)
     {
         INT cur_node_sum = new INT(0);
         return subTree_exists(root, cur_node_sum, sum);
     }
     public static void main(String args[])
     {
         Node root = newnode(5);
         root.left = newnode(4);
         root.right = newnode(3);
         root.left.left = newnode(3);
         root.left.right = newnode(2);
         root.right.left = newnode(2);
         root.right.right = newnode(1);
         
         int sum = 6;
         if (sumSubtree(root, sum))
             System.out.println("Subtree with the given sum " + sum + " exists");
          else
             System.out.println("Subtree with the given sum does not exist");
     }
}

 

Output:

Subtree with the given sum 6 exists

 

Let us analyze the time and complexity of this approach.

Complexity analysis

Time complexity

This approach will take O( n ) where n is the number of nodes in the tree. The complexity of post-order traversal is also the same.

Space complexity

And it will take O(1). Since we are not using any extra space to store the result. We are simply returning if the subtree exists or not. 

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

What exactly is a Red-Black tree data structure?

The Red-Black tree is a type of self-balancing tree with the following characteristics:

  • Each node is either red or black in color.
  • The root is always black in color.
  • There can be no red parents or children for a red node.
  • There is the same number of black nodes on every path from the root node to a NULL node.

How do you determine whether a binary tree is a subtree of another binary tree?

Consider the binary tree T. We now want to see if a binary tree S is a subtree of a binary tree T. To begin, see if you can find a node in T that is also in S. Once you've found this common node, see if the nodes below are also a part of S. If this is the case, we can confidently conclude that S is a subtree of T.

What are tree traversal algorithms?

There are three tree traversal algorithms: preorder, postorder and inorder.

In preorder, we traverse the root node first, then the left node, and then the right node.

In postorder, we traverse the left node first, then the right node, and then the root node.

In inorder, we traverse the left node first, then the root node, and then the right node.

Conclusion

To conclude this blog, firstly we discussed the problem statement if there exists a subtree with a given sum in a binary tree and different examples to understand the problem statement. For the recursive approach, we discussed its algorithm, implementations, and complexities. 

 

Recommended problems -

 

For more content, Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

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 Learning!

Previous article
Exponential Levels of a Binary Tree
Next article
Symmetric Binary Tree
Live masterclass