Subtree with given sum in a Binary Tree - GeeksforGeeks

Subtree with given sum in a Binary Tree - GeeksforGeeks
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.

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

// 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);

}

Read full article from Subtree with given sum in a Binary Tree - GeeksforGeeks