Subtree with given sum in a Binary Tree

Last Updated : 11 Sep, 2023

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> 

Output

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

Output

Yes

Time complexity : – O(N)
Auxiliary Space :- O(N)

Shashank Mishra ( Gullu )

Improve

Program to Determine if given Two Trees are Identical or not

Succinct Encoding of Binary Tree

Types of Binary Tree

Some important Binary tree traversals

Easy problems on Binary Tree

Intermediate problems on Binary Tree

Hard problems on Binary Tree

Subtree with given sum in a Binary Tree

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?