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;
}
You can also try this code with Online C++ Compiler
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");
}
}
You can also try this code with Online Java Compiler
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 Algorithms, Competitive Programming, JavaScript, System 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 problems, interview 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!
8+ registered 