Tutorialspoint.dev

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 exist 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 tree in Postorder fashion because here we have to think bottom-up . First calculate the sum of left subtree then right subtree and check if sum_left + sum_right + cur_node = sum is satisfying the condition that means any subtree with given sum exist. Below is the recursive implementation of 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


Output:

Yes

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

tags:

Tree Tree

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter