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














































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




More Articles of Dhiraj Sharma:

Name Views Likes
Python program to find subtree with given sum in a binary tree 504 18
C++ program to find check if given sorted sub-sequence exists in binary search tree 548 20

Comments