Given a Binary Tree. Return true if, for every node X in the tree other than the leaves, its value is equal to the sum of its left subtree's value and its right subtree's value. Else return false.
An empty tree is also a Sum Tree as the sum of an empty tree can be considered to be 0. A leaf node is also considered a Sum Tree.
Example 1:
Input:
    3
  /   \    
 1     2
Output: 1
Explanation:
The sum of left subtree and right subtree is
1 + 2 = 3, which is the value of the root node.
Therefore,the given binary tree is a sum tree.
Example 2:
Input:
          10
        /    \
      20      30
    /   \ 
   10    10
Output: 0
Explanation:
The given tree is not a sum tree.
For the root node, sum of elements
in left subtree is 40 and sum of elements
in right subtree is 30. Root element = 10
which is not equal to 30+40.
Your Task:  
You don't need to read input or print anything. Complete the function isSumTree() which takes root node as input parameter and returns true if the tree is a SumTree else it returns false.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(Height of the Tree)
Constraints:
1 ≤ number of nodes ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: '''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''

# your task is to complete this function

# function should return True is Tree is SumTree else return False

class Solution:

    def isSumTree(self,root):

        # Code here



Solutions:
class Solution:

	def isSumTree(self, root):
		if root.left is None and root.right is None:
			return True
		x = 0
		if root.left:
			self.isSumTree(root.left)
			x += root.left.data
		if root.right:
			self.isSumTree(root.right)
			x += root.right.data
		if x == root.data:
			root.data *= 2
			return True
		else:
			return False


class Solution:

	def isSumTree(self, root):
		f = []
		Solution.SumTree(self, root, f)
		if len(f) == 0:
			return True
		return False

	def SumTree(self, root, f):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		a = Solution.SumTree(self, root.left, f)
		b = Solution.SumTree(self, root.right, f)
		x = root.data
		if x != a + b:
			f.append(0)
		return a + b + x


class Solution:

	def isSumTree(self, root):

		def sum(root):
			if root == None:
				return 0
			l = sum(root.left)
			r = sum(root.right)
			return l + r + root.data

		def sumTree(root):
			if root == None or (root.left == None and root.right == None):
				return True
			elif root.data != sum(root.left) + sum(root.right):
				return False
			return sumTree(root.left) and sumTree(root.right)
		return sumTree(root)


class Solution:

	def isSumTree(self, root):
		ans = solution(root)
		return ans[1]

def solution(root):
	if root == None:
		return [0, True]
	if root.left == None and root.right == None:
		return [root.data, True]
	left = solution(root.left)
	right = solution(root.right)
	ans = [0, True]
	sm = left[0] + right[0]
	if left[1] and right[1] and (root.data == sm):
		ans[0] = sm + root.data
	else:
		ans[1] = False
	return ans


class Solution:

	def isSumTree(self, root):

		def dfs(root):
			if root is None:
				return [True, 0]
			if root.left is None and root.right is None:
				return [True, root.data]
			(left, right) = (dfs(root.left), dfs(root.right))
			boolean = root.data == left[1] + right[1]
			if left and right and boolean:
				return [True, left[1] + right[1] + root.data]
			else:
				return [False, root.data]
		return dfs(root)[0]


class Solution:

	def isSumTree(self, root):
		issum = True

		def summTree(root):
			nonlocal issum
			if root is None:
				return 0
			if root.left is None and root.right is None:
				return root.data
			if issum is False:
				return 0
			a = summTree(root.left)
			b = summTree(root.right)
			if root.data != a + b:
				issum = False
			ans = a + b + root.data
			return ans
		summTree(root)
		return issum


class Solution:

	def util(self, node):
		if node:
			if not node.left and (not node.right):
				return [node.data, True]
			if not node.left:
				rgt = self.util(node.right)
				return [2 * node.data, node.data == rgt[0] and rgt[-1]]
			if not node.right:
				rgt = self.util(node.left)
				return [2 * node.data, node.data == rgt[0] and rgt[-1]]
			lft = self.util(node.left)
			rgt = self.util(node.right)
			return [2 * node.data, node.data == lft[0] + rgt[0] and lft[-1] and rgt[-1]]

	def isSumTree(self, root):
		return self.util(root)[-1]


class Solution:

	def isSumTree(self, root):

		def sum(root):
			if root is None:
				return 0
			return sum(root.left) + root.data + sum(root.right)
		if root == None or (root.left == None and root.right == None):
			return 1
		ls = sum(root.left)
		rs = sum(root.right)
		if ls + rs == root.data and self.isSumTree(root.left) and self.isSumTree(root.right):
			return 1
		return 0


class Solution:

	def isSumTree(self, root):
		ans = [1]

		def solve(root):
			if root:
				if not root.right and (not root.left):
					return root.data
				else:
					if root.left:
						a = solve(root.left)
					else:
						a = 0
					if root.right:
						b = solve(root.right)
					else:
						b = 0
					if a + b == root.data:
						return 2 * root.data
					else:
						ans[0] = 0
						return root.data
		solve(root)
		return ans[0]


import sys

class Solution:

	def util(self, root):
		if root == None:
			return [1, 0]
		if root.left == None and root.right == None:
			return [1, root.data]
		l = self.util(root.left)
		r = self.util(root.right)
		if l[0] == 1 and r[0] == 1:
			if l[1] + r[1] == root.data:
				return [1, l[1] + r[1] + root.data]
			else:
				return [0, sys.maxsize]
		else:
			return [0, sys.maxsize]

	def isSumTree(self, root):
		ans = self.util(root)
		return ans[0]


class Solution:

	def solve(self, root):
		if root is None:
			return [0, True]
		elif root.left is None and root.right is None:
			return [root.data, True]
		(l, r) = (self.solve(root.left), self.solve(root.right))
		if l[0] + r[0] != root.data or l[1] == False or r[1] == False:
			return [l[0] + r[0] + root.data, False]
		else:
			return [2 * root.data, True]

	def isSumTree(self, root):
		return self.solve(root)[1]


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

class Solution:

	def isSumTree(self, root):
		if root is None:
			return True
		if root.left is None and root.right is None:
			return True
		left_sum = self.sum(root.left)
		right_sum = self.sum(root.right)
		if root.data == left_sum + right_sum and self.isSumTree(root.left) and self.isSumTree(root.right):
			return True
		return False

	def sum(self, root):
		if root is None:
			return 0
		return root.data + self.sum(root.left) + self.sum(root.right)


class Solution:

	def __init__(self):
		self.flag = 1

	def fun(self, root):
		if root.left is None and root.right is None:
			return root.data
		x = 0
		y = 0
		if root.left is not None:
			x = self.fun(root.left)
		if root.right is not None:
			y = self.fun(root.right)
		if x + y != root.data:
			self.flag = 0
		return x + y + root.data

	def isSumTree(self, root):
		self.fun(root)
		return self.flag


class Solution:

	def solve(self, root):
		if root == None:
			return 0
		left = self.solve(root.left)
		right = self.solve(root.right)
		if root.left == None and root.right == None:
			return root.data
		if root.data != left + right:
			self.flg = 0
		return left + right + root.data

	def isSumTree(self, root):
		self.flg = 1
		self.solve(root)
		if self.flg == 0:
			return False
		else:
			return True


class Solution:

	def solve(self, root):
		if root is None:
			return (True, 0)
		elif root.left is None and root.right is None:
			return (True, root.data)
		left = self.solve(root.left)
		right = self.solve(root.right)
		is_left = left[0]
		is_right = right[0]
		is_sum = left[1] + right[1] == root.data
		if is_left and is_right and is_sum:
			return (True, left[1] + right[1] + root.data)
		return (False, -1)

	def isSumTree(self, root):
		res = self.solve(root)
		return res[0]


class Solution:

	def isSumTree(self, root):
		res = [True]

		def findSum(root, res):
			if root == None:
				return 0
			l = findSum(root.left, res)
			r = findSum(root.right, res)
			if l == 0 and r == 0:
				return root.data
			res[0] = res[0] and l + r == root.data
			return l + r + root.data
		findSum(root, res)
		return res[0]


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

class Solution:

	def sum(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return root.data
		if self.f == 0:
			return 0
		left = self.sum(root.left)
		right = self.sum(root.right)
		if left + right != root.data:
			self.f = 0
		return left + right + root.data

	def isSumTree(self, root):
		self.f = 1
		self.sum(root)
		return self.f


class Solution:

	def isSumTree(self, root):

		def isLeaf(node):
			if node == None:
				return 0
			if node.left == None and node.right == None:
				return 1
			return 0

		def sum(root):
			if root == None:
				return 0
			return sum(root.left) + root.data + sum(root.right)
			if node == None or isLeaf(node):
				return 1

		def solve(node):
			if node == None or isLeaf(node):
				return 1
			if solve(node.left) and solve(node.right):
				if node.left == None:
					ls = 0
				elif isLeaf(node.left):
					ls = node.left.data
				else:
					ls = 2 * node.left.data
				if node.right == None:
					rs = 0
				elif isLeaf(node.right):
					rs = node.right.data
				else:
					rs = 2 * node.right.data
				return node.data == ls + rs
			return 0
		return bool(solve(root))


class Solution:

	def isSumTree(self, root):

		def isSumTreeUtil(node):
			if not node:
				return 0
			lsum = isSumTreeUtil(node.left)
			rsum = isSumTreeUtil(node.right)
			if lsum == 0 and rsum == 0:
				return lsum + rsum + node.data
			if node.data != lsum + rsum or lsum == -1 or rsum == -1:
				return -1
			return lsum + rsum + node.data
		return isSumTreeUtil(root) != -1


class Solution:

	def isSumTree(self, root):
		if root is None or (root.left is None and root.right is None):
			return 1
		self.isSumTree(root.left)
		self.isSumTree(root.right)
		if root.data == self.findSum(root.left) + self.findSum(root.right) and self.isSumTree(root.left) and self.isSumTree(root.right):
			return 1
		return 0

	def findSum(self, root):
		if root is None:
			return 0
		left_sum = self.findSum(root.left)
		right_sum = self.findSum(root.right)
		return root.data + left_sum + right_sum