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
Read full article from 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 rootbool 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);}