Subtree with given sum in a Binary Tree
You are given a binary tree and a given sum. The task is to check if there exists a subtree whose sum of all nodes is equal to the given sum.
Examples :
// For above tree
Input : sum = 17
Output: “Yes”
// sum of all nodes of subtree {3, 5, 9} = 17
Input : sum = 11
Output: “No”
// no subtree with given sum exist
The idea is to traverse the tree in a Postorder fashion because here we have to think bottom-up. First, calculate the sum of the left subtree then the right subtree, and check if sum_left + sum_right + cur_node = sum is satisfying the condition that means any subtree with a given sum exists. Below is the recursive implementation of the algorithm.
C++
// C++ program to find if there is a subtree with // given sum #include<bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node { int data; struct Node* left, *right; }; /* utility that allocates a new node with the given data and NULL left and right pointers. */ struct Node* newnode( int data) { struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node); } // function to check if there exist any subtree with given sum // 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 sumSubtreeUtil( struct Node *ptr, int *cur_sum, int sum) { // base condition if (ptr == NULL) { *cur_sum = 0; return false ; } // Here first we go to left sub-tree, then right subtree // then first we calculate sum of all nodes of subtree // having ptr as root and assign it as cur_sum // cur_sum = sum_left + sum_right + ptr->data // after that we check if cur_sum == sum int sum_left = 0, sum_right = 0; return ( sumSubtreeUtil(ptr->left, &sum_left, sum) || sumSubtreeUtil(ptr->right, &sum_right, sum) || ((*cur_sum = sum_left + sum_right + ptr->data) == sum)); } // Wrapper over sumSubtreeUtil() bool sumSubtree( struct Node *root, int sum) { // Initialize sum of subtree with root int cur_sum = 0; return sumSubtreeUtil(root, &cur_sum, sum); } // driver program to run the case int main() { struct Node *root = newnode(8); root->left = newnode(5); root->right = newnode(4); root->left->left = newnode(9); root->left->right = newnode(7); root->left->right->left = newnode(1); root->left->right->right = newnode(12); root->left->right->right->right = newnode(2); root->right->right = newnode(11); root->right->right->left = newnode(3); int sum = 22; if (sumSubtree(root, sum)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program to find if there // is a subtree with given sum import java.util.*; class GFG { /* A binary tree node has data, pointer to left child and a pointer to right child */ static class Node { int data; Node left, right; } static class INT { int v; INT( int a) { v = a; } } /* utility that allocates a new node with the given data and null left and right pointers. */ static Node newnode( int data) { Node node = new Node(); node.data = data; node.left = node.right = null ; return (node); } // function to check if there exist // any subtree with given sum // 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 sumSubtreeUtil(Node ptr, INT cur_sum, int sum) { // base condition if (ptr == null ) { cur_sum = new INT( 0 ); return false ; } // Here first we go to left // sub-tree, then right subtree // then first we calculate sum // of all nodes of subtree having // ptr as root and assign it as // cur_sum. (cur_sum = sum_left + // sum_right + ptr.data) after that // we check if cur_sum == sum INT sum_left = new INT( 0 ), sum_right = new INT( 0 ); return (sumSubtreeUtil(ptr.left, sum_left, sum) || sumSubtreeUtil(ptr.right, sum_right, sum) || ((cur_sum.v = sum_left.v + sum_right.v + ptr.data) == sum)); } // Wrapper over sumSubtreeUtil() static boolean sumSubtree(Node root, int sum) { // Initialize sum of // subtree with root INT cur_sum = new INT( 0 ); return sumSubtreeUtil(root, cur_sum, sum); } // Driver Code public static void main(String args[]) { Node root = newnode( 8 ); root.left = newnode( 5 ); root.right = newnode( 4 ); root.left.left = newnode( 9 ); root.left.right = newnode( 7 ); root.left.right.left = newnode( 1 ); root.left.right.right = newnode( 12 ); root.left.right.right.right = newnode( 2 ); root.right.right = newnode( 11 ); root.right.right.left = newnode( 3 ); int sum = 22 ; if (sumSubtree(root, sum)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed // by Arnab Kundu |
Python3
# Python3 program to find if there is a # subtree with given sum # Binary Tree Node """ utility that allocates a newNode with the given key """ class newnode: # Construct to create a newNode def __init__( self , key): self .data = key self .left = None self .right = None # function to check if there exist any # subtree with given sum # 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 def sumSubtreeUtil(ptr,cur_sum, sum ): # base condition if (ptr = = None ): cur_sum[ 0 ] = 0 return False # Here first we go to left sub-tree, # then right subtree then first we # calculate sum of all nodes of subtree # having ptr as root and assign it as cur_sum # cur_sum = sum_left + sum_right + ptr.data # after that we check if cur_sum == sum sum_left, sum_right = [ 0 ], [ 0 ] x = sumSubtreeUtil(ptr.left, sum_left, sum ) y = sumSubtreeUtil(ptr.right, sum_right, sum ) cur_sum[ 0 ] = (sum_left[ 0 ] + sum_right[ 0 ] + ptr.data) return ((x or y) or (cur_sum[ 0 ] = = sum )) # Wrapper over sumSubtreeUtil() def sumSubtree(root, sum ): # Initialize sum of subtree with root cur_sum = [ 0 ] return sumSubtreeUtil(root, cur_sum, sum ) # Driver Code if __name__ = = '__main__' : root = newnode( 8 ) root.left = newnode( 5 ) root.right = newnode( 4 ) root.left.left = newnode( 9 ) root.left.right = newnode( 7 ) root.left.right.left = newnode( 1 ) root.left.right.right = newnode( 12 ) root.left.right.right.right = newnode( 2 ) root.right.right = newnode( 11 ) root.right.right.left = newnode( 3 ) sum = 22 if (sumSubtree(root, sum )) : print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10) |
C#
using System; // C# program to find if there // is a subtree with given sum public class GFG { /* A binary tree node has data, pointer to left child and a pointer to right child */ public class Node { public int data; public Node left, right; } public class INT { public int v; public INT( int a) { v = a; } } /* utility that allocates a new node with the given data and null left and right pointers. */ public static Node newnode( int data) { Node node = new Node(); node.data = data; node.left = node.right = null ; return (node); } // function to check if there exist // any subtree with given sum // 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 public static bool sumSubtreeUtil(Node ptr, INT cur_sum, int sum) { // base condition if (ptr == null ) { cur_sum = new INT(0); return false ; } // Here first we go to left // sub-tree, then right subtree // then first we calculate sum // of all nodes of subtree having // ptr as root and assign it as // cur_sum. (cur_sum = sum_left + // sum_right + ptr.data) after that // we check if cur_sum == sum INT sum_left = new INT(0), sum_right = new INT(0); return (sumSubtreeUtil(ptr.left, sum_left, sum) || sumSubtreeUtil(ptr.right, sum_right, sum) || ((cur_sum.v = sum_left.v + sum_right.v + ptr.data) == sum)); } // Wrapper over sumSubtreeUtil() public static bool sumSubtree(Node root, int sum) { // Initialize sum of // subtree with root INT cur_sum = new INT(0); return sumSubtreeUtil(root, cur_sum, sum); } // Driver Code public static void Main( string [] args) { Node root = newnode(8); root.left = newnode(5); root.right = newnode(4); root.left.left = newnode(9); root.left.right = newnode(7); root.left.right.left = newnode(1); root.left.right.right = newnode(12); root.left.right.right.right = newnode(2); root.right.right = newnode(11); root.right.right.left = newnode(3); int sum = 22; if (sumSubtree(root, sum)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by Shrikant13 |
Javascript
<script> // javascript program to find if there // is a subtree with given sum /* * A binary tree node has data, pointer to left child and a pointer to right * child */ class Node { constructor(){ this .data = 0; this .left = null ; this .right = null ; } } class INT { constructor(a) { this .v = a; } } /* * utility that allocates a new node with the given data and null left and right * pointers. */ function newnode(data) { var node = new Node(); node.data = data; node.left = node.right = null ; return (node); } // function to check if there exist // any subtree with given sum // 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 function sumSubtreeUtil( ptr, cur_sum , sum) { // base condition if (ptr == null ) { cur_sum = new INT(0); return false ; } // Here first we go to left // sub-tree, then right subtree // then first we calculate sum // of all nodes of subtree having // ptr as root and assign it as // cur_sum. (cur_sum = sum_left + // sum_right + ptr.data) after that // we check if cur_sum == sum var sum_left = new INT(0), sum_right = new INT(0); return (sumSubtreeUtil(ptr.left, sum_left, sum) || sumSubtreeUtil(ptr.right, sum_right, sum) || ((cur_sum.v = sum_left.v + sum_right.v + ptr.data) == sum)); } // Wrapper over sumSubtreeUtil() function sumSubtree( root, sum) { // Initialize sum of // subtree with root var cur_sum = new INT(0); return sumSubtreeUtil(root, cur_sum, sum); } // Driver Code var root = newnode(8); root.left = newnode(5); root.right = newnode(4); root.left.left = newnode(9); root.left.right = newnode(7); root.left.right.left = newnode(1); root.left.right.right = newnode(12); root.left.right.right.right = newnode(2); root.right.right = newnode(11); root.right.right.left = newnode(3); var sum = 22; if (sumSubtree(root, sum)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by Rajput-Ji </script> |
Yes
Time Complexity: O(N), As we are visiting every node once.
Auxiliary space: O(h), Here h is the height of the tree and the extra space is used due to the recursion call stack.
Approach 2:-
- Initialize a hash map mp to store the frequency of each sum encountered along the root-to-leaf paths of the binary tree.
- Add a dummy entry in the map with sum 0 to handle the case where the root itself has the target sum.
- Initialize a stack st and push the root node onto it.
- While the stack is not empty, pop the top node curr from the stack.
- Update the sum as sum + curr->val.
- Check if the difference sum – targetSum exists in the hash map. If it does, then return true.
- Otherwise, add the current sum sum to the hash map with a frequency of 1.
- If the current node has a right child, push it onto the stack.
- If the current node has a left child, push it onto the stack.
- If the stack becomes empty, return false.
C++
#include <bits/stdc++.h> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode( int x) : val(x) , left(NULL) , right(NULL) { } }; bool hasTargetSum(TreeNode* root, int targetSum) { unordered_map< int , int > mp; mp[0] = 1; // adding a dummy sum to handle the case // where root itself has the target sum int sum = 0; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* curr = st.top(); st.pop(); sum += curr->val; if (mp.find(sum - targetSum) != mp.end()) { return true ; } mp[sum] = 1; if (curr->right) { st.push(curr->right); } if (curr->left) { st.push(curr->left); } } return false ; } int main() { /* 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 */ TreeNode* root = new TreeNode(5); root->left = new TreeNode(4); root->left->left = new TreeNode(11); root->left->left->left = new TreeNode(7); root->left->left->right = new TreeNode(2); root->right = new TreeNode(8); root->right->left = new TreeNode(13); root->right->right = new TreeNode(4); root->right->right->right = new TreeNode(1); int targetSum = 22; if (hasTargetSum(root, targetSum)) { cout << "Yes" ; } else { cout << "No" ; } return 0; } |
Java
// Java implementation of above approach import java.util.*; // Create tree node class TreeNode { int val; TreeNode left; TreeNode right; TreeNode( int x) { val = x; } } class Solution { // Function to check the target public boolean hasTargetSum(TreeNode root, int targetSum) { HashMap<Integer, Integer> map = new HashMap<>(); map.put( 0 , 1 ); // adding a dummy sum to handle the case // where root itself has the target sum int sum = 0 ; // Using stack to push node Stack<TreeNode> stack = new Stack<>(); stack.push(root); // Looping the stack while (!stack.empty()) { TreeNode curr = stack.pop(); sum += curr.val; if (map.containsKey( sum - targetSum)) { // checking target return true ; } map.put(sum, 1 ); if (curr.right != null ) { // calling the right node stack.push(curr.right); } if (curr.left != null ) { // calling the left node stack.push(curr.left); } } return false ; } public static void main(String[] args) { // Taken Tree /* 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 */ // Input tree TreeNode root = new TreeNode( 5 ); root.left = new TreeNode( 4 ); root.left.left = new TreeNode( 11 ); root.left.left.left = new TreeNode( 7 ); root.left.left.right = new TreeNode( 2 ); root.right = new TreeNode( 8 ); root.right.left = new TreeNode( 13 ); root.right.right = new TreeNode( 4 ); root.right.right.right = new TreeNode( 1 ); int targetSum = 22 ; Solution solution = new Solution(); if (solution.hasTargetSum(root, targetSum)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } |
Python3
# Python implementation of above approach from collections import defaultdict # Create tree node class TreeNode: def __init__( self , val = 0 , left = None , right = None ): self .val = val self .left = left self .right = right # Function to check the target def hasTargetSum(root, targetSum): mp = defaultdict( int ) mp[ 0 ] = 1 # adding a dummy sum to handle the case # where root itself has the target sum stack = [root] # Using stack to push node sum = 0 # Looping the stack while stack: curr = stack.pop() sum + = curr.val if sum - targetSum in mp: # checking target return True mp[ sum ] = 1 if curr.right: stack.append(curr.right) # calling the right node if curr.left: stack.append(curr.left) # calling the left node return False """ 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 """ # Driver code root = TreeNode( 5 ) root.left = TreeNode( 4 ) root.left.left = TreeNode( 11 ) root.left.left.left = TreeNode( 7 ) root.left.left.right = TreeNode( 2 ) root.right = TreeNode( 8 ) root.right.left = TreeNode( 13 ) root.right.right = TreeNode( 4 ) root.right.right.right = TreeNode( 1 ) targetSum = 22 if hasTargetSum(root, targetSum): print ( "Yes" ) else : print ( "No" ) |
C#
using System; using System.Collections.Generic; public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode( int x) { val = x; } } public class Solution { public bool HasTargetSum(TreeNode root, int targetSum) { Dictionary< int , int > mp = new Dictionary< int , int >(); mp[0] = 1; // adding a dummy sum to handle the case // where root itself has the target sum int sum = 0; Stack<TreeNode> st = new Stack<TreeNode>(); st.Push(root); while (st.Count != 0) { TreeNode curr = st.Pop(); sum += curr.val; if (mp.ContainsKey( sum - targetSum)) { // check if the // difference exists // in the dictionary return true ; } mp[sum] = 1; // add the sum to the dictionary if (curr.right != null ) { st.Push( curr.right); // add the right child to // the stack if it exists } if (curr.left != null ) { st.Push( curr.left); // add the left child to the // stack if it exists } } return false ; } } public class Program { static void Main( string [] args) { /* 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 */ TreeNode root = new TreeNode(5); root.left = new TreeNode(4); root.left.left = new TreeNode(11); root.left.left.left = new TreeNode(7); root.left.left.right = new TreeNode(2); root.right = new TreeNode(8); root.right.left = new TreeNode(13); root.right.right = new TreeNode(4); root.right.right.right = new TreeNode(1); int targetSum = 22; Solution sol = new Solution(); if (sol.HasTargetSum( root, targetSum)) { // check if the target sum // exists in the tree Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } |
Javascript
// Definition for a binary tree node. function TreeNode(val) { this .val = val; this .left = this .right = null ; } function hasTargetSum(root, targetSum) { const map = new Map(); map.set(0, 1); // adding a dummy sum to handle the case // where root itself has the target sum let sum = 0; const stack = []; stack.push(root); while (stack.length > 0) { const curr = stack.pop(); sum += curr.val; if (map.has(sum - targetSum)) { return true ; } map.set(sum, 1); if (curr.right) { stack.push(curr.right); } if (curr.left) { stack.push(curr.left); } } return false ; } /* 5 / 4 8 / / 11 13 4 / \ 7 2 1 */ const root = new TreeNode(5); root.left = new TreeNode(4); root.left.left = new TreeNode(11); root.left.left.left = new TreeNode(7); root.left.left.right = new TreeNode(2); root.right = new TreeNode(8); root.right.left = new TreeNode(13); root.right.right = new TreeNode(4); root.right.right.right = new TreeNode(1); const targetSum = 22; if (hasTargetSum(root, targetSum)) { console.log( "Yes" ); // expected output: "Yes" } else { console.log( "No" ); // expected output: "No" } // This code is contributed by sarojmcy2e |
Yes
Time complexity : – O(N)
Auxiliary Space :- O(N)
Contact Us