Python program to check if a given binary tree is sumtree
Description:
A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.
Get the sum of nodes in left subtree and right subtree. Check if the sum calculated is equal to root%u2019s data. Also, recursively check if the left and right subtrees are SumTrees.
Program:
class Node(object):
def __init__(self,data):
self.val = data
self.left = None
self.right = None
def find_sum(root):
if root is None:
return 0
return (find_sum(root.right) + root.val + find_sum(root.left))
def Check_Sumtree(root):
if (root is None) or ((root.left is None) and (root.right is None)):
return 1
l_count = find_sum(root.left)
r_count = find_sum(root.right)
if((root.val == l_count+ r_count) and (Check_Sumtree(root.left) and(Check_Sumtree(root.right)))):
return 1
return 0
def main():
root = Node(44)
root.left = Node(9)
root.right = Node(13)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
if (Check_Sumtree(root)):
print('The Given Tree is Sum Tree')
else:
print('The Given Tree is Not Sum tree')
if __name__ == "__main__":
main()
Output:
The Given Tree is Sum Tree
Comments