Given a Binary Tree of size N , where each node can have positive or negative values. Convert this to a tree where each node contains the sum of the left and right sub trees of the original tree. The values of leaf nodes are changed to 0.
Example 1:
Input:
             10
          /      \
        -2        6
       /   \     /  \
     8     -4   7    5
Output:
            20
          /    \
        4        12
       /  \     /  \
     0     0   0    0
Explanation:
           (4-2+12+6)
          /           \
      (8-4)          (7+5)
       /   \         /  \
      0     0       0    0
 
Your Task:  
You dont need to read input or print anything. Complete the function toSumTree() which takes root node as input parameter and modifies the given tree in-place.
Note: If you click on Compile and Test the output will be the in-order traversal of the modified tree.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)
 
Constraints:
1 ≤ N ≤ 10^{4}

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:
    def toSumTree(self, root) :
        #code here

Solutions:
class Solution:

	def toSumTree(self, root):
		if root == None:
			return 0
		a = Solution.toSumTree(self, root.left)
		b = Solution.toSumTree(self, root.right)
		x = root.data
		root.data = a + b
		return x + a + b


class Solution:

	def toSumTree(self, root):
		ll = rr = 0
		if root.left:
			l = root.left.data
			self.toSumTree(root.left)
			ll = l + root.left.data
		if root.right:
			r = root.right.data
			self.toSumTree(root.right)
			rr = r + root.right.data
		root.data = ll + rr
		return root


class Solution:

	def toSumTree(self, root):
		if root == None:
			return 0
		old_val = root.data
		l = self.toSumTree(root.left)
		r = self.toSumTree(root.right)
		root.data = l + r
		return old_val + root.data


class Solution:

	def toSumTree(self, root):
		r = root
		return self.t(r)

	def t(self, rt):
		if rt is None:
			return 0
		if rt.left is None and rt.right is None:
			d = rt.data
			rt.data = 0
			return d
		r = rt.data
		rt.data = self.t(rt.left) + self.t(rt.right)
		return r + rt.data


class Solution:

	def toSumTree(self, root):

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


class Solution:

	def toSumTree(self, root):
		if root == None:
			return 0
		l = self.toSumTree(root.left)
		r = self.toSumTree(root.right)
		summ = l + r
		x = root.data
		root.data = summ
		return summ + x


class Solution:

	def toSumTree(self, root):
		temp = 0
		if not root:
			return 0
		temp = root.data
		root.data = self.toSumTree(root.left) + self.toSumTree(root.right)
		return temp + root.data


def slove(root):
	if root is None:
		return 0
	oldval = root.data
	root.data = slove(root.left) + slove(root.right)
	return oldval + root.data

class Solution:

	def toSumTree(self, root):
		slove(root)
		return


class Solution:

	def toSumTree(self, root):
		if root == None:
			return 0
		sumLeft = self.toSumTree(root.left)
		sumRight = self.toSumTree(root.right)
		tmp = root.data
		root.data = sumLeft + sumRight
		return tmp + root.data


class Solution:

	def sumi(self, root):
		if root == None:
			return 0
		val = root.data
		root.data = self.sumi(root.left) + self.sumi(root.right)
		return root.data + val

	def toSumTree(self, root):
		self.sumi(root)
		return root


class Solution:

	def toSumTree(self, root):

		def dfs(root):
			if not root:
				return 0
			old = root.data
			left = dfs(root.left)
			right = dfs(root.right)
			root.data = left + right
			return old + root.data
		return dfs(root)


class Solution:

	def toSumTree(self, root):

		def sumofNodes(root):
			if root is None:
				return 0
			return root.data + (sumofNodes(root.left) + sumofNodes(root.right))
		if root is None:
			return
		if root.left is None and root.right is None:
			root.data = 0
		root.data = sumofNodes(root.left) + sumofNodes(root.right)
		self.toSumTree(root.left)
		self.toSumTree(root.right)


class Solution:

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

	def toSumTree(self, root):
		data = self.rec_sol(root)
		return root


class Solution:

	def toSumTree(self, root):

		def fun(root):
			if root is None:
				return 0
			x = root.data
			root.data = fun(root.left) + fun(root.right)
			return x + root.data

		def printInorder(root, l):
			if root is None:
				return
			if root.left:
				printInorder(root.left, l)
			l.append(root.data)
			if root.right:
				printInorder(root.right, l)
			return
		fun(root)
		l = []
		printInorder(root, l)
		return l


class Solution:

	def toSumTree(self, root):
		if root is None:
			return 0
		x = self.toSumTree(root.left)
		y = self.toSumTree(root.right)
		a = root.data
		root.data = x + y
		return a + root.data


class Solution:

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

	def toSumTree(self, root):
		if root is None:
			return
		root.data = self.subTreeSum(root.left) + self.subTreeSum(root.right)
		self.toSumTree(root.left)
		self.toSumTree(root.right)


class Solution:

	def toSumTree(self, root):
		root.data = self.solve(root.left) + self.solve(root.right)
		return root

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


class Solution:

	def toSumTree(self, root):

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


class Solution:

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


class Solution:

	def toSumTree(self, root):

		def h(root):
			if root == None:
				return 0
			left = h(root.left)
			right = h(root.right)
			cur = root.data
			root.data = left + right
			return root.data + cur
		h(root)
		return root


class Solution:

	def solve(self, root):
		if not root:
			return 0
		a = self.solve(root.left)
		b = self.solve(root.right)
		x = root.data
		root.data = a + b
		return root.data + x

	def toSumTree(self, root):
		return self.solve(root)


class Info:

	def __init__(self, act, summ):
		self.act = act
		self.summ = summ

def transform(root):
	if root.left == None and root.right == None:
		info = Info(root.data, 0)
		root.data = 0
		return info
	else:
		if root.left:
			linfo = transform(root.left)
		else:
			linfo = Info(0, 0)
		if root.right:
			rinfo = transform(root.right)
		else:
			rinfo = Info(0, 0)
		info = Info(root.data, linfo.act + rinfo.act + linfo.summ + rinfo.summ)
		root.data = info.summ
		return info

class Solution:

	def toSumTree(self, root):
		if root == None:
			return root
		else:
			transform(root)
			return root


class Solution:

	def toSumTree(self, root):

		def post(root, l, r):
			if root is None:
				return 0
			l = post(root.left, l, r)
			r = post(root.right, l, r)
			temp = root.data
			root.data = l + r
			return temp + root.data
		r = post(root, 0, 0)
		return r


class Solution:

	def toSumTree(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			t = root.data
			root.data = 0
			return t
		l = self.toSumTree(root.left)
		r = self.toSumTree(root.right)
		t1 = root.data
		root.data = l + r
		s = l + r + t1
		return s


class Solution:

	def toSumTree(self, root):

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


class Solution:

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

	def toSumTree(self, root):
		self.solve(root)


class Solution:

	def toSumTree(self, root):
		if root is None:
			return 0
		ls = self.toSumTree(root.left)
		rs = self.toSumTree(root.right)
		x = root.data
		root.data = ls + rs
		return ls + rs + x


class Solution:

	def toSumTree(self, root):

		def transform(root):
			if not root:
				return 0
			l = transform(root.left)
			r = transform(root.right)
			temp = root.data
			root.data = l + r
			return temp + l + r
		transform(root)
		return root


class Solution:

	def toSumTree(self, root):
		if not root:
			return 0
		lh = self.toSumTree(root.left)
		rh = self.toSumTree(root.right)
		x = root.data
		root.data = lh + rh
		return lh + rh + x


def Sum(root):
	if root == None:
		return 0
	temp1 = Sum(root.left)
	temp2 = Sum(root.right)
	temp = root.data
	root.data = temp1 + temp2
	return temp1 + temp2 + temp

class Solution:

	def toSumTree(self, root):
		ans = Sum(root)
		return root


class Solution:

	def toSumTree(self, root):

		def f(root):
			if root == None:
				return 0
			lh = f(root.left)
			rh = f(root.right)
			x = root.data
			root.data = lh + rh
			return x + lh + rh
		f(root)


class Solution:

	def toSumTree(self, root):

		def postorder(root):
			if root == None:
				return 0
			a = postorder(root.left)
			b = postorder(root.right)
			root.data = a + b + root.data
			return root.data
		postorder(root)
		q = deque()
		q.append(root)
		while q:
			n = q.popleft()
			sl = 0
			sr = 0
			if n.left == None and n.right == None:
				n.data = 0
				continue
			if n.left:
				sl = n.left.data
				q.append(n.left)
			if n.right:
				sr = n.right.data
				q.append(n.right)
			n.data = sl + sr
		return root


class Solution:

	def toSumTree(self, root):

		def rec(root):
			if root == None:
				return 0
			left_sum = rec(root.left)
			right_sum = rec(root.right)
			old = root.data
			root.data = left_sum + right_sum
			return old + left_sum + right_sum
		rec(root)


class Solution:

	def toSumTree(self, Node):
		if Node == None:
			return 0
		old_val = Node.data
		Node.data = self.toSumTree(Node.left) + self.toSumTree(Node.right)
		return Node.data + old_val


class Node:

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

class Solution:

	def toSumTree(self, root):
		vis = {}
		if not root:
			return []
		stack = [root]
		result = []
		parent = {}
		parent[root] = Node(0)
		temp = [root]
		mval = {}
		while temp:
			top = temp.pop()
			mval[top] = top.data
			if top.left:
				temp.append(top.left)
				vis[top.left] = False
				parent[top.left] = top
			if top.right:
				temp.append(top.right)
				vis[top.right] = False
				parent[top.right] = top
		while stack:
			top = stack[-1]
			if top.left and (not vis[top.left]):
				stack.append(top.left)
				vis[top.left] = True
			elif top.right and (not vis[top.right]):
				stack.append(top.right)
				vis[top.right] = True
			else:
				node = stack.pop()
				parent[node].data += node.data
				node.data -= mval[node]
		return root


class Solution:

	def solve(self, root):
		if root is None:
			return 0
		l = self.toSumTree(root.left)
		r = self.toSumTree(root.right)
		x = root.data
		root.data = l + r
		return x + l + r

	def toSumTree(self, root):
		return self.solve(root)


class Solution:

	def toSumTree(self, root):
		if root == None:
			return 0
		o = root.data
		root.data = self.toSumTree(root.left) + self.toSumTree(root.right)
		return root.data + o


class Solution:

	def toSumTree(self, root):
		if not root:
			return 0
		leftsum = self.toSumTree(root.left)
		rightsum = self.toSumTree(root.right)
		value = root.data + leftsum + rightsum
		root.data = leftsum + rightsum
		return value


class Solution:

	def toSumTree(self, root):

		def dfs(root, sm):
			if not root:
				return 0
			left = dfs(root.left, sm)
			right = dfs(root.right, sm)
			if not root.left and (not root.right):
				sm += root.data
				root.data = 0
			else:
				sm = left + right
				temp = root.data
				root.data = sm
				sm += temp
			return sm
		return dfs(root, 0)


class Solution:

	def toSumTree(self, root):

		def sumTree(root):
			if root is None:
				return (root, 0)
			value = root.data
			root.data = sumTree(root.left)[1] + sumTree(root.right)[1]
			return (root, root.data + value)
		return sumTree(root)[0]


class Solution:

	def toSumTree(self, root):

		def sumTree(root):
			if root is None:
				return (root, 0)
			(root_l, leftVal) = sumTree(root.left)
			(root_r, rightVal) = sumTree(root.right)
			leftData = 0
			rightData = 0
			rootVal = root.data
			if root.left:
				leftData = root.left.data
			if root.right:
				rightData = root.right.data
			root.data = leftData + rightData + leftVal + rightVal
			return (root, rootVal)
		return sumTree(root)[0]


class Solution:

	def toSumTree(self, root):
		if root is None:
			return root
		self.sum_tree_util(root)
		return root

	def sum_tree_util(self, root):
		if root is None:
			return [0, True]
		if root.left is None and root.right is None:
			val = root.data
			root.data = 0
			return [val, True]
		if root.left is not None:
			left_node_val = root.left.data
		else:
			left_node_val = 0
		if root.right is not None:
			right_node_val = root.right.data
		else:
			right_node_val = 0
		left_sum_val_terminating = self.sum_tree_util(root.left)
		right_sum_val_terminating = self.sum_tree_util(root.right)
		if right_sum_val_terminating[1]:
			final_right_sum = right_sum_val_terminating[0]
		else:
			final_right_sum = right_node_val + right_sum_val_terminating[0]
		if left_sum_val_terminating[1]:
			final_left_sum = left_sum_val_terminating[0]
		else:
			final_left_sum = left_node_val + left_sum_val_terminating[0]
		root.data = final_left_sum + final_right_sum
		return [final_left_sum + final_right_sum, False]


class Solution:

	def toSumTree(self, root):

		def makesumtree(root):
			if root == None:
				return 0
			lefts = makesumtree(root.left)
			rights = makesumtree(root.right)
			val = root.data
			root.data = lefts + rights
			return val + lefts + rights
		makesumtree(root)


class Solution:

	def toSumTree(self, root):

		def DFS(node):
			if not node:
				return 0
			temp = node.data
			if not node.left and (not node.right):
				node.data = 0
				return temp
			node.data = DFS(node.left) + DFS(node.right)
			return temp + node.data
		DFS(root)
		return root


class Solution:

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

	def toSumTree(self, root):
		self.SumTree(root)
		return root


class Solution:

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

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


class Solution:

	def toSumTree(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			a = root.data
			root.data = 0
			return a
		ls = self.toSumTree(root.left)
		rs = self.toSumTree(root.right)
		a = root.data
		root.data = ls + rs
		return a + ls + rs


class Solution:

	def toSumTree(self, root):
		if not root:
			return 0
		a = self.toSumTree(root.left)
		b = self.toSumTree(root.right)
		c = root.data
		sum1 = a + b
		root.data = sum1
		return sum1 + c


class Solution:

	def toSumTree(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			temp = root.data
			root.data = 0
			return temp
		tempa = root.data
		root.data = self.toSumTree(root.left) + self.toSumTree(root.right)
		return root.data + tempa


class Solution:

	def toSumTree(self, root):

		def dfs(node):
			if not node:
				return 0
			left = dfs(node.left)
			right = dfs(node.right)
			res = left + right + node.data
			node.data = left + right
			return res
		dfs(root)


class Solution:

	def toSumTree(self, root):

		def su(root):
			(left, right) = (0, 0)
			if root.left:
				left = root.left.data + su(root.left)
			if root.right:
				right = root.right.data + su(root.right)
			root.data = left + right
			return root.data
		su(root)


class Solution:

	def toSumTree(self, root):
		return self.solve(root)

	def solve(self, root):
		if root == None:
			return 0
		a = self.solve(root.left)
		b = self.solve(root.right)
		c = root.data
		root.data = a + b
		return root.data + c


class Solution:

	def n(self, root):
		if root == None:
			return
		self.n(root.left)
		self.n(root.right)
		if root.left == None and root.right == None:
			root.data = 0

	def post(self, root, a):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		lv = self.post(root.left, a)
		rv = self.post(root.right, a)
		a = root.data
		root.data = lv + rv
		return root.data + a

	def toSumTree(self, root):
		root.data = 0
		self.post(root, 0)
		self.n(root)


class Solution:

	def toSumTree(self, root):

		def dfs(root):
			if not root:
				return 0
			l_s = dfs(root.left)
			r_s = dfs(root.right)
			s = root.data + l_s + r_s
			root.data = l_s + r_s
			return s
		return dfs(root)


class Solution:

	def toSumTree(self, root):
		if not root:
			return 0
		ls = self.toSumTree(root.left)
		rs = self.toSumTree(root.right)
		x = root.data
		root.data = ls + rs
		return ls + rs + x


class Solution:

	def toSumTree(self, root):

		def helper(root):
			if root:
				lv = helper(root.left)
				rv = helper(root.right)
				c = root.data
				root.data = lv + rv
				return root.data + c
			else:
				return 0
		helper(root)


class Solution:

	def toSumTree(self, root):
		if not root:
			return 0
		newVal = 0
		if root.left:
			leftVal = self.toSumTree(root.left)
			newVal += leftVal
		if root.right:
			rightVal = self.toSumTree(root.right)
			newVal += rightVal
		val = root.data
		root.data = newVal
		return val + root.data