Given a Binary Tree. Check whether all of its nodes have the value equal to the sum of their child nodes.
Example 1:
Input:
     10
    /
  10 
Output: 1
Explanation: Here, every node is sum of
its left and right child.
Example 2:
Input:
       1
     /   \
    4     3
   /  \
  5    N
Output: 0
Explanation: Here, 1 is the root node
and 4, 3 are its child nodes. 4 + 3 =
7 which is not equal to the value of
root node. Hence, this tree does not
satisfy the given conditions.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isSumProperty() that takes the root Node of the Binary Tree as input and returns 1 if all the nodes in the tree satisfy the following properties. Else, it returns 0.
For every node, data value must be equal to the sum of data values in left and right children. Consider data value as 0 for NULL child.  Also, leaves are considered to follow the property.
Expected Time Complexiy: O(N).
Expected Auxiliary Space: O(Height of the Tree).
 
Constraints:
1 <= N <= 10^{5}
1 <= Data on nodes <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

'''
# Node Class:
class Node:
    def init(self,val):
        self.data = val
        self.left = None
        self.right = None
'''

class Solution:
    #Function to check whether all nodes of a tree have the value 
    #equal to the sum of their child nodes.
    def isSumProperty(self, root):
        # code here


Solutions:
class Solution:

	def isSumProperty(self, root):
		if not root or not (root.left or root.right):
			return 1
		l = 0
		r = 0
		if root.left:
			l = root.left.data
		if root.right:
			r = root.right.data
		if root.data == l + r and self.isSumProperty(root.left) and self.isSumProperty(root.right):
			return 1
		else:
			return 0


class Solution:

	def isSumProperty(self, root):
		l = [root]
		while l != []:
			lv = 0
			rv = 0
			p = l.pop()
			if p.left == None and p.right == None:
				continue
			else:
				if p.left != None:
					lv = p.left.data
					l.insert(0, p.left)
				if p.right != None:
					rv = p.right.data
					l.insert(0, p.right)
			if lv + rv != p.data:
				return 0
		if l == []:
			return 1


class Solution:

	def isSumProperty(self, root):
		res = [1]

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


class Solution:

	def isSumProperty(self, root):
		if not root.left and (not root.right):
			return 1
		left = right = 1
		if root.left:
			left = self.isSumProperty(root.left)
		if root.right:
			right = self.isSumProperty(root.right)
		leftval = root.left.data if root.left else 0
		rightval = root.right.data if root.right else 0
		return 1 if (left and right) and leftval + rightval == root.data else 0


class Solution:

	def isSumProperty(self, root):
		if root == None:
			return 1
		if root.left == None and root.right == None:
			return 1
		s = 0
		if root.left != None:
			s += root.left.data
		if root.right != None:
			s += root.right.data
		return int(s == root.data and self.isSumProperty(root.left) and self.isSumProperty(root.right))


class Solution:

	def isSumProperty(self, root):
		if root is None:
			return 1
		if root.left is None and root.right is None:
			return 1
		val_root = root.data
		(lval, rval) = (0, 0)
		if root.left is not None:
			lval = root.left.data
		if root.right is not None:
			rval = root.right.data
		if val_root != lval + rval:
			return 0
		return self.isSumProperty(root.left) & self.isSumProperty(root.right)


class Solution:

	def _solve(self, node):
		if not node:
			return 1
		if not node.left and (not node.right):
			return 1
		sum = 0
		if node.left:
			sum += node.left.data
		if node.right:
			sum += node.right.data
		if node.data == sum and self._solve(node.left) and self._solve(node.right):
			return 1
		return 0

	def isSumProperty(self, root):
		ans = self._solve(root)
		return ans


class Solution:

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


class Solution:

	def isSumProperty(self, root):
		b = []
		Solution.bst(root, b)
		for i in b:
			if i.left and i.right:
				if i.left.data + i.right.data != i.data:
					return 0
			elif i.left:
				if i.left.data != i.data:
					return 0
			elif i.right:
				if i.right.data != i.data:
					return 0
		return 1

	def bst(root, b):
		if root.left:
			Solution.bst(root.left, b)
		b.append(root)
		if root.right:
			Solution.bst(root.right, b)


class Solution:

	def isSumProperty(self, root):
		if root is None:
			return 1
		if root.left is None and root.right is None:
			return 1
		if self.isSumProperty(root.left) == 0 or self.isSumProperty(root.right) == 0:
			return 0
		leftval = 0
		if root.left is not None:
			leftval = root.left.data
		rightval = 0
		if root.right is not None:
			rightval = root.right.data
		return int(root.data == leftval + rightval)


class Solution:

	def isSumProperty(self, root):
		return isSumProperty(root)

def isSumProperty(node):
	left_data = 0
	right_data = 0
	if node == None or (node.left == None and node.right == None):
		return 1
	else:
		if node.left != None:
			left_data = node.left.data
		if node.right != None:
			right_data = node.right.data
		if node.data == left_data + right_data and isSumProperty(node.left) and isSumProperty(node.right):
			return 1
		else:
			return 0


class Solution:

	def isSumProperty(self, root):
		if root == None:
			return
		q = deque()
		q.append(root)
		while q:
			node = q.popleft()
			a = node.data
			b = 0
			c = 0
			if node.left:
				q.append(node.left)
				b = node.left.data
			if node.right:
				q.append(node.right)
				c = node.right.data
			if node.left or node.right:
				if a != b + c:
					return 0
		return 1


class Solution:

	def isSumProperty(self, root):
		if not root:
			return 1
		if root.left and root.right:
			if root.data == root.left.data + root.right.data:
				return self.isSumProperty(root.left) and self.isSumProperty(root.right)
			else:
				return 0
		elif root.left and (not root.right):
			if root.data == root.left.data:
				return self.isSumProperty(root.left)
			else:
				return 0
		elif root.right and (not root.left):
			if root.data == root.right.data:
				return self.isSumProperty(root.right)
			else:
				return 0
		else:
			return 1


class Solution:

	def isSumProperty(self, root):
		if root is None:
			return 1
		if root.left is None and root.right is None:
			return 1
		val_root = root.data
		(val_left, val_right) = (0, 0)
		if root.left is not None:
			val_left = root.left.data
		if root.right is not None:
			val_right = root.right.data
		if val_root != val_left + val_right:
			return 0
		return self.isSumProperty(root.left) & self.isSumProperty(root.right)


from collections import deque

class Solution:

	def isSumProperty(self, root):
		queue = deque([root])
		while queue:
			node = queue.popleft()
			s = 0
			if node.left:
				s += node.left.data
				queue.append(node.left)
			if node.right:
				s += node.right.data
				queue.append(node.right)
			if s != 0:
				if s != node.data:
					return 0
		return 1


from collections import deque

class Solution:

	def isSumProperty(self, root):
		if root is None:
			return 1
		if root.left == None and root.right == None:
			return 1
		left = root.left.data if root.left != None else 0
		right = root.right.data if root.right != None else 0
		if root.data != left + right:
			return 0
		if self.isSumProperty(root.left) == 1 and self.isSumProperty(root.right) == 1:
			return 1
		else:
			return 0


class Solution:

	def isSumProperty(self, root):
		if root is None:
			return 1
		if root.left is None and root.right is None:
			return 1
		lh = root.left.data if root.left else 0
		rh = root.right.data if root.right else 0
		if lh + rh == root.data and self.isSumProperty(root.left) and self.isSumProperty(root.right):
			return 1
		else:
			return 0


class Solution:

	def isSumProperty(self, root):
		s = [root]
		while s:
			node = s.pop()
			if node.left or node.right:
				sm = 0
				if node.left:
					s.append(node.left)
					sm += node.left.data
				if node.right:
					s.append(node.right)
					sm += node.right.data
				if sm != node.data:
					return 0
		return 1


class Solution:

	def isSumProperty(self, root):
		if root is None:
			return 1
		if root.left is None and root.right is None:
			return 1
		l = root.left.data if root.left else 0
		r = root.right.data if root.right else 0
		if l + r == root.data and self.isSumProperty(root.left) and self.isSumProperty(root.right):
			return 1
		else:
			return 0


class Solution:

	def __init__(self):
		self.ans = 1

	def sum_recursive(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return root.data
		ls = self.sum_recursive(root.left)
		rs = self.sum_recursive(root.right)
		s = ls + rs
		if s != root.data:
			self.ans = 0
		return root.data

	def isSumProperty(self, root):
		self.sum_recursive(root)
		return self.ans


class Solution:

	def isSumProperty(self, root):
		add_ = 0
		if root is None or (root.left is None and root.right is None):
			return 1
		else:
			if root.left != None:
				add_ += root.left.data
			if root.right != None:
				add_ += root.right.data
			if add_ == root.data and self.isSumProperty(root.left) and self.isSumProperty(root.right):
				return 1
			else:
				return 0


class Solution:

	def isSumProperty(self, root):
		childsum = 0
		ans = 0
		if not root:
			return 1
		if root.left:
			childsum += root.left.data
		if root.right:
			childsum += root.right.data
		if not root.left and (not root.right):
			ans = 1
		elif root.data == childsum:
			ans = 1
		return ans and self.isSumProperty(root.left) and self.isSumProperty(root.right)


from collections import deque

class Solution:

	def isSumProperty(self, root):
		queue = deque([root])
		while queue:
			n = len(queue)
			for i in range(n):
				node = queue.popleft()
				if node.left and node.right:
					if node.data != node.left.data + node.right.data:
						return 0
					queue.append(node.left)
					queue.append(node.right)
				elif not node.left and (not node.right):
					continue
				elif not node.left:
					if node.data != node.right.data:
						return 0
					queue.append(node.right)
				elif not node.right:
					if node.data != node.left.data:
						return 0
					queue.append(node.left)
		return 1


class Solution:

	def isSumProperty(self, root):
		if root:
			if not root.left and (not root.right):
				return 1
			res = root.data
			left = root.left.data if root.left else 0
			right = root.right.data if root.right else 0
			if left + right != res:
				return 0
			lh = self.isSumProperty(root.left)
			if not lh:
				return 0
			rh = self.isSumProperty(root.right)
			if not rh:
				return 0
			return 1
		return 1


class Solution:

	def isSumProperty(self, root):
		q = []
		q.append(root)
		while len(q):
			temp = q.pop(0)
			if temp.left is not None:
				q.append(temp.left)
				a = temp.left.data
			if temp.right is not None:
				q.append(temp.right)
				b = temp.right.data
			if temp.left == None:
				a = 0
			if temp.right == None:
				b = 0
			if temp.left == None and temp.right == None:
				x = temp.data
			else:
				x = a + b
			if x == temp.data:
				flag = 1
			else:
				return 0
		return flag


class Solution:

	def isSumProperty(self, root):
		ls = 0
		rs = 0
		if root == None or (root.left == None and root.right == None):
			return 1
		else:
			if root.left:
				ls = root.left.data
			if root.right:
				rs = root.right.data
			if root.data == ls + rs and self.isSumProperty(root.left) and self.isSumProperty(root.right):
				return 1
			return 0


class Solution:

	def isSumProperty(self, root):

		def checkSum(root):
			if root is None:
				return 1
			if root.left is None and root.right is None:
				return 1
			if root.left:
				lSum = root.left.data
			if not root.left:
				lSum = 0
			if root.right:
				rSum = root.right.data
			if not root.right:
				rSum = 0
			if root.data != lSum + rSum:
				return 0
			if root.data == lSum + rSum and (checkSum(root.left) and checkSum(root.right)):
				return 1
			return 0
		return checkSum(root)


class Solution:

	def isSumProperty(self, root):
		if root == None:
			return 1
		if root.left == None:
			if root.right == None:
				return 1
			lf = 0
		else:
			lf = root.left.data
		if root.right == None:
			rf = 0
		else:
			rf = root.right.data
		if root.data == lf + rf and self.isSumProperty(root.left) and self.isSumProperty(root.right):
			return 1
		else:
			return 0


class Solution:

	def isSumProperty(self, root):

		def fun(root):
			ans = 1
			if root is None:
				return 1
			if root.left is None and root.right is None:
				return 1
			if root.left:
				ans = ans and fun(root.left)
			if root.right:
				ans = ans and fun(root.right)
			if root.left:
				a = root.left.data
			else:
				a = 0
			if root.right:
				b = root.right.data
			else:
				b = 0
			if root.data - (a + b) == 0:
				return ans
			return 0
		t = fun(root)
		return t


def summ(root):
	if root is None:
		return 1
	if root.left == None and root.right == None:
		return 1
	valroot = root.data
	valleft = 0
	valright = 0
	if root.left is not None:
		valleft = root.left.data
	if root.right is not None:
		valright = root.right.data
	if valroot != valleft + valright:
		return 0
	return summ(root.left) and summ(root.right)

class Solution:

	def isSumProperty(self, root):
		return summ(root)


class Solution:

	def isSumProperty(self, root):

		def ans(root):
			if not root:
				return (1, 0)
			if not root.left and (not root.right):
				return (1, root.data)
			(ls, lt) = ans(root.left)
			(rs, rt) = ans(root.right)
			if not ls or not rs:
				return (0, lt + rt)
			if root.data != lt + rt:
				return (0, lt + rt)
			return (1, lt + rt)
		(sta, answ) = ans(root)
		return sta


class Solution:

	def dfs(self, node):
		if not node.left and (not node.right):
			return 1
		left = right = 0
		if node.left:
			if self.dfs(node.left) == 0:
				return 0
			left = node.left.data
		if node.right:
			if self.dfs(node.right) == 0:
				return 0
			right = node.right.data
		if left + right != node.data:
			return 0
		return 1

	def isSumProperty(self, root):
		return self.dfs(root)


class Solution:

	def isSumProperty(self, root):
		return self.issum(root)

	def issum(self, node):
		if node is None:
			return 1
		if not node.left and (not node.right):
			return 1
		if not node.left:
			left = 0
		else:
			left = node.left.data
		if not node.right:
			right = 0
		else:
			right = node.right.data
		if left + right != node.data:
			return 0
		return self.issum(node.left) and self.issum(node.right)


class Solution:

	def isSumProperty(self, root):

		def dfs(cur):
			if cur is None:
				return [True, 0]
			left = dfs(cur.left)
			right = dfs(cur.right)
			child_sum = left[1] + right[1]
			equal_child = (cur.left or cur.right) and child_sum == cur.data or (not cur.left and (not cur.right))
			return [left[0] and right[0] and equal_child, cur.data]
		return 1 if dfs(root)[0] else 0


class Solution:

	def isSumProperty(self, root):

		def sol(root):
			if not root:
				return [True, 0]
			left = sol(root.left)
			right = sol(root.right)
			if root.left and root.right:
				return [root.data == left[1] + right[1] and left[0] and right[0], root.data]
			elif root.left:
				return [root.data == left[1] and left[0] and right[0], root.data]
			elif root.right:
				return [root.data == right[1] and left[0] and right[0], root.data]
			else:
				return [True, root.data]
		(boolean, val) = sol(root)
		return 1 if boolean == True else 0


class Solution:

	def isSumProperty(self, root):
		self.res = True

		def f(root):
			if root == None:
				return 0
			if root.left != None or root.right != None:
				a = root.left.data if root.left != None else 0
				b = root.right.data if root.right != None else 0
				cur = root.data == a + b
				if cur == False:
					self.res = cur
			f(root.left)
			f(root.right)
		ans = f(root)
		if self.res:
			return 1
		return 0


class Solution:

	def isSumProperty(self, root):
		if root == None:
			return 1
		if root.left == None and root.right == None:
			return 1
		valroot = root.data
		(l, r) = (0, 0)
		if root.left != None:
			l = root.left.data
		if root.right != None:
			r = root.right.data
		if valroot != l + r:
			return 0
		a = self.isSumProperty(root.left)
		b = self.isSumProperty(root.right)
		return a & b


class Solution:

	def isSumProperty(self, root):
		leftdata = 0
		rightdata = 0
		if not root or (not root.left and (not root.right)):
			return 1
		else:
			if root.left:
				leftdata = root.left.data
			if root.right:
				rightdata = root.right.data
			if root.data == leftdata + rightdata and Solution().isSumProperty(root.left) and Solution().isSumProperty(root.right):
				return 1
			else:
				return 0


class Solution:

	def isSumProperty(self, root):
		if root == None or (root.left == None and root.right == None):
			return 1
		lsum = 0
		rsum = 0
		if root.left != None:
			lsum = root.left.data
		if root.right != None:
			rsum = root.right.data
		if root.data == lsum + rsum and self.isSumProperty(root.left) and self.isSumProperty(root.right):
			return 1
		return 0


class Solution:

	def isSumProperty(self, root):
		List = []

		def transverse(root):
			if root == None:
				return
			Sum = 0
			if root.left != None:
				Sum = Sum + root.left.data
			if root.right != None:
				Sum = Sum + root.right.data
			if Sum != root.data and root.left != root.right:
				List.append(0)
			transverse(root.left)
			transverse(root.right)
		transverse(root)
		if List == []:
			return 1
		else:
			return 0


class Solution:

	def isSumProperty(self, root):

		def hh(root):
			if root == None:
				return 1
			lh = hh(root.left)
			rh = hh(root.right)
			if root.left == None and root.right == None:
				return 1
			k1 = 0
			if lh == 0 or rh == 0:
				return 0
			if root.left:
				k1 += root.left.data
			if root.right:
				k1 += root.right.data
			if k1 == root.data:
				return 1
			return 0
		return hh(root)


class Solution:

	def isSumProperty(self, root):
		self.ans = True

		def recursive(root):
			if root is None:
				return 1
			if root.left is None and root.right is None:
				return 1
			s = 0
			if root.left:
				s += root.left.data
			if root.right:
				s += root.right.data
			return 1 if root.data == s and recursive(root.left) and recursive(root.right) else 0
		return 1 if recursive(root) else 0


from collections import deque

class Solution:

	def isSumProperty(self, root):
		if not root:
			return True
		q = deque()
		q.append(root)
		while q:
			node = q.popleft()
			s = 0
			if node.left:
				s += node.left.data
				q.append(node.left)
			if node.right:
				s += node.right.data
				q.append(node.right)
			if s and s != node.data:
				return 0
		return 1


class Solution:

	def isSumProperty(self, root):

		def f(node):
			l = 0
			r = 0
			if node is None or (node.left is None and node.right is None):
				return 1
			if node.left:
				l = node.left.data
			if node.right:
				r = node.right.data
			if l + r != node.data:
				return 0
			return f(node.left) and f(node.right)
		return f(root)


from collections import deque

class Solution:

	def isSumProperty(self, root):
		q = deque()
		if root == None:
			return 1
		q.append(root)
		while len(q) != 0:
			temp = q.popleft()
			val1 = 0
			val2 = 0
			if temp.left == None and temp.right == None:
				continue
			if temp.left != None:
				val1 = temp.left.data
				q.append(temp.left)
			if temp.right != None:
				val2 = temp.right.data
				q.append(temp.right)
			if temp.data != val1 + val2:
				return 0
		return 1


class Solution:

	def answer(self, root, flag):
		if not root:
			return
		if not root.right and (not root.left):
			return
		sum = 0
		if root.left:
			sum += root.left.data
		if root.right:
			sum += root.right.data
		if sum != root.data:
			flag.append(1)
			return False
		self.answer(root.left, flag)
		self.answer(root.right, flag)
		return

	def isSumProperty(self, root):
		flag = []
		self.answer(root, flag)
		if flag == []:
			return 1
		return 0


class Solution:

	def isSumProperty(self, root):
		if self.check(root):
			return 1
		else:
			return 0

	def check(self, root):
		if root is None:
			return True
		leftdata = root.left.data if root.left else 0
		rightdata = root.right.data if root.right else 0
		if not root.left and (not root.right):
			return True
		return root.data == leftdata + rightdata and self.check(root.left) and self.check(root.right)


class Solution:

	def isSumProperty(self, node):
		if node is None:
			return 1
		leftval = 0
		rightval = 0
		if node.left:
			leftval = node.left.data
		if node.right:
			rightval = node.right.data
		if node.left or node.right:
			if node.data != leftval + rightval:
				return 0
		if self.isSumProperty(node.left) and self.isSumProperty(node.right):
			return 1
		return 0


class Solution:

	def isSumProperty(self, node):
		if node is None:
			return 1
		leftVal = 0
		rightVal = 0
		if node.left:
			leftVal = node.left.data
		if node.right:
			rightVal = node.right.data
		if node.left or node.right:
			if node.data != rightVal + leftVal:
				return 0
		if self.isSumProperty(node.left) and self.isSumProperty(node.right):
			return 1
		return 0


class Solution:

	def isSumProperty(self, root):
		if not root or (not root.left and (not root.right)):
			return 1
		childrenSum = 0
		if root.left:
			childrenSum += root.left.data
		if root.right:
			childrenSum += root.right.data
		return (root.data == childrenSum) & self.isSumProperty(root.left) & self.isSumProperty(root.right)


class Solution:

	def isSumProperty(self, root):

		def solve(root):
			if not root:
				return 0
			if root.left == None and root.right == None:
				return root.data
			t = solve(root.left)
			t1 = solve(root.right)
			if t != -1 and t1 != -1 and (t + t1 == root.data):
				return root.data
			else:
				return -1
		a = solve(root)
		if a == -1:
			return 0
		else:
			return 1


from queue import Queue

class Solution:

	def isSumProperty(self, root):
		q = Queue()
		q.put(root)
		q.put(None)
		while not q.empty():
			curr = q.get()
			if curr == None:
				if not q.empty():
					q.put(None)
				continue
			sum = 0
			if curr.left:
				q.put(curr.left)
				sum += curr.left.data
			if curr.right:
				q.put(curr.right)
				sum += curr.right.data
			if sum != curr.data and sum != 0:
				return 0
		return 1


class Solution:

	def isSumProperty(self, root):
		if not root:
			return

		def check(temp):
			if temp == None or (temp.left == None and temp.right == None):
				return True
			a = temp.left.data if temp.left else 0
			b = temp.right.data if temp.right else 0
			return a + b == temp.data and check(temp.left) and check(temp.right)
		return 1 if check(root) else 0


class Solution:

	def isSumProperty(self, root):
		res = [1]
		self.helper(root, res)
		return res[0]

	def helper(self, root, res):
		if not root:
			return 0
		l = self.helper(root.left, res)
		r = self.helper(root.right, res)
		if l + r != 0 and l + r != root.data:
			res[0] = 0
		return root.data


class Solution:

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

	def isSumProperty(self, root):
		if root == None:
			return 1
		return self.solve(root)