Given a binary tree containing n nodes. The problem is to count subtress having total node’s data sum equal to a given value x.
Examples:
Input :
5
/
-10 3
/ /
9 8 -4 7
x = 7
Output : 2
There are 2 subtrees with sum 7.
1st one is leaf node:
7.
2nd one is:
-10
/
9 8
Source: Microsoft Interview Experience | Set 157.
Algorithm:
countSubtreesWithSumX(root, count, x)
if !root then
return 0
ls = countSubtreesWithSumX(root->left, count, x)
rs = countSubtreesWithSumX(root->right, count, x)
sum = ls + rs + root->data
if sum == x then
count++
return sum
countSubtreesWithSumXUtil(root, x)
if !root then
return 0
Initialize count = 0
ls = countSubtreesWithSumX(root->left, count, x)
rs = countSubtreesWithSumX(root->right, count, x)
if (ls + rs + root->data) == x
count++
return count
C++
// C++ implementation to count subtress that // sum up to a given value x #include <bits/stdc++.h> using namespace std; // structure of a node of binary tree struct Node { int data; Node *left, *right; }; // function to get a new node Node* getNode(int data) { // allocate space Node* newNode = (Node*)malloc(sizeof(Node)); // put in the data newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // function to count subtress that // sum up to a given value x int countSubtreesWithSumX(Node* root, int& count, int x) { // if tree is empty if (!root) return 0; // sum of nodes in the left subtree int ls = countSubtreesWithSumX(root->left, count, x); // sum of nodes in the right subtree int rs = countSubtreesWithSumX(root->right, count, x); // sum of nodes in the subtree rooted // with 'root->data' int sum = ls + rs + root->data; // if true if (sum == x) count++; // return subtree's nodes sum return sum; } // utility function to count subtress that // sum up to a given value x int countSubtreesWithSumXUtil(Node* root, int x) { // if tree is empty if (!root) return 0; int count = 0; // sum of nodes in the left subtree int ls = countSubtreesWithSumX(root->left, count, x); // sum of nodes in the right subtree int rs = countSubtreesWithSumX(root->right, count, x); // if tree's nodes sum == x if ((ls + rs + root->data) == x) count++; // required count of subtrees return count; } // Driver program to test above int main() { /* binary tree creation 5 / -10 3 / / 9 8 -4 7 */ Node* root = getNode(5); root->left = getNode(-10); root->right = getNode(3); root->left->left = getNode(9); root->left->right = getNode(8); root->right->left = getNode(-4); root->right->right = getNode(7); int x = 7; cout << "Count = " << countSubtreesWithSumXUtil(root, x); return 0; } |
Java
// Java program to find if // there is a subtree with // given sum import java.util.*; class GFG { // structure of a node // of binary tree static class Node { int data; Node left, right; } static class INT { int v; INT(int a) { v = a; } } // function to get a new node static Node getNode(int data) { // allocate space Node newNode = new Node(); // put in the data newNode.data = data; newNode.left = newNode.right = null; return newNode; } // function to count subtress that // sum up to a given value x static int countSubtreesWithSumX(Node root, INT count, int x) { // if tree is empty if (root == null) return 0; // sum of nodes in the left subtree int ls = countSubtreesWithSumX(root.left, count, x); // sum of nodes in the right subtree int rs = countSubtreesWithSumX(root.right, count, x); // sum of nodes in the subtree // rooted with 'root.data' int sum = ls + rs + root.data; // if true if (sum == x) count.v++; // return subtree's nodes sum return sum; } // utility function to // count subtress that // sum up to a given value x static int countSubtreesWithSumXUtil(Node root, int x) { // if tree is empty if (root == null) return 0; INT count = new INT(0); // sum of nodes in the left subtree int ls = countSubtreesWithSumX(root.left, count, x); // sum of nodes in the right subtree int rs = countSubtreesWithSumX(root.right, count, x); // if tree's nodes sum == x if ((ls + rs + root.data) == x) count.v++; // required count of subtrees return count.v; } // Driver Code public static void main(String args[]) { /* binary tree creation 5 / -10 3 / / 9 8 -4 7 */ Node root = getNode(5); root.left = getNode(-10); root.right = getNode(3); root.left.left = getNode(9); root.left.right = getNode(8); root.right.left = getNode(-4); root.right.right = getNode(7); int x = 7; System.out.println("Count = " + countSubtreesWithSumXUtil(root, x)); } } // This code is contributed // by Arnab Kundu |
Python3
# Python3 implementation to count subtress
# that Sum up to a given value x
# class to get a new node
class getNode:
def __init__(self, data):
# put in the data
self.data = data
self.left = self.right = None
# function to count subtress that
# Sum up to a given value x
def countSubtreesWithSumX(root, count, x):
# if tree is empty
if (not root):
return 0
# Sum of nodes in the left subtree
ls = countSubtreesWithSumX(root.left,
count, x)
# Sum of nodes in the right subtree
rs = countSubtreesWithSumX(root.right,
count, x)
# Sum of nodes in the subtree
# rooted with ‘root.data’
Sum = ls + rs + root.data
# if true
if (Sum == x):
count[0] += 1
# return subtree’s nodes Sum
return Sum
# utility function to count subtress
# that Sum up to a given value x
def countSubtreesWithSumXUtil(root, x):
# if tree is empty
if (not root):
return 0
count = [0]
# Sum of nodes in the left subtree
ls = countSubtreesWithSumX(root.left,
count, x)
# Sum of nodes in the right subtree
rs = countSubtreesWithSumX(root.right,
count, x)
# if tree’s nodes Sum == x
if ((ls + rs + root.data) == x):
count[0] += 1
# required count of subtrees
return count[0]
# Driver Code
if __name__ == ‘__main__’:
# binary tree creation
# 5
# /
# -10 3
# / /
# 9 8 -4 7
root = getNode(5)
root.left = getNode(-10)
root.right = getNode(3)
root.left.left = getNode(9)
root.left.right = getNode(8)
root.right.left = getNode(-4)
root.right.right = getNode(7)
x = 7
print(“Count =”,
countSubtreesWithSumXUtil(root, x))
# This code is contributed by PranchalK
C#
using System; // c# program to find if // there is a subtree with // given sum public class GFG { // structure of a node // of binary tree public class Node { public int data; public Node left, right; } public class INT { public int v; public INT(int a) { v = a; } } // function to get a new node public static Node getNode(int data) { // allocate space Node newNode = new Node(); // put in the data newNode.data = data; newNode.left = newNode.right = null; return newNode; } // function to count subtress that // sum up to a given value x public static int countSubtreesWithSumX(Node root, INT count, int x) { // if tree is empty if (root == null) { return 0; } // sum of nodes in the left subtree int ls = countSubtreesWithSumX(root.left, count, x); // sum of nodes in the right subtree int rs = countSubtreesWithSumX(root.right, count, x); // sum of nodes in the subtree // rooted with 'root.data' int sum = ls + rs + root.data; // if true if (sum == x) { count.v++; } // return subtree's nodes sum return sum; } // utility function to // count subtress that // sum up to a given value x public static int countSubtreesWithSumXUtil(Node root, int x) { // if tree is empty if (root == null) { return 0; } INT count = new INT(0); // sum of nodes in the left subtree int ls = countSubtreesWithSumX(root.left, count, x); // sum of nodes in the right subtree int rs = countSubtreesWithSumX(root.right, count, x); // if tree's nodes sum == x if ((ls + rs + root.data) == x) { count.v++; } // required count of subtrees return count.v; } // Driver Code public static void Main(string[] args) { /* binary tree creation 5 / -10 3 / / 9 8 -4 7 */ Node root = getNode(5); root.left = getNode(-10); root.right = getNode(3); root.left.left = getNode(9); root.left.right = getNode(8); root.right.left = getNode(-4); root.right.right = getNode(7); int x = 7; Console.WriteLine("Count = " + countSubtreesWithSumXUtil(root, x)); } } // This code is contributed by Shrikant13 |
Output:
Count = 2
Time Complexity: O(n).
leave a comment
0 Comments