## Introduction

Here in this blog, we are asked to see various approaches to find a subtree with a given sum in a binary tree. We already are familiar with the concept of the subtree and binary tree and also its features and implementations. So, let's dig a little deeper into this blog.

*Source: *__binary tree__

### Problem Statement

In this problem, we are provided a binary tree and also a sum and we are asked to find if there exists a subtree whose sum of all the nodes is equal to the given sum. If that subtree exists, we have to print yes else print no. Let us understand the problem statement with the help of an example. We need to keep in mind that for the binary tree If the level of the root is zero, a binary tree can have a maximum of 2l nodes at level l.

When each binary tree node has one or two children, the number of leaf nodes (nodes with no children) is one greater than the number of nodes with two children.

### Sample Example

**Explanation:** Suppose our given sum is 6. So we have to find if there is any subtree in this binary tree that has the sum of its node 6. If we look closely, we will see that there exists one subtree with a sum 6. The right child of root node here is 3,the children of 3 are 2 and 1. So the sum of three nodes = 6, which is equal to our target sum. So we can say that, yes, a subtree exists.

Here the approach we will be using is the sum of the current subtree= sum of the left subtree + sum of right subtree + value of current node.

Here, the sum of the current subtree = 3 + 2 + 1 = 6, which is equal to the sum.

From the above diagram, we can clearly understand the problem statement and the approach we will use to solve it.

## Recursive Approach

This approach is very simple to implement and straightforward. Recursion is commonly used to solve tree questions. We use recursion to solve this problem as well.

As with most Binary tree problems, we start with the traversal. In this case, traversing the tree in post-order makes sense. While post traversing, we will keep in mind that sum of the current subtree = the sum of the left subtree + the sum of the right subtree + the value of the current node.

Let us see its algorithm.

### Steps Of Algorithm

**Step 1: **If the root is null, return false.

**Step 2:** We will calculate the sum of the left subtree.

**Step 3: **Then we will calculate the sum of the right subtree.

**Step 4:** In the end, we will check for the condition sum_left_tree + sum_right_tree + current_node = given_sum.

**Step 5:** If this condition exists, that means the subtree exists with the given sum and we will simply print yes.

Let us see the implementation of this approach in the next section of this blog.