### Python program to find subtree with given sum in a binary tree

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.

# 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")