Given a Binary Tree of size N , where each node can have positive or negative values. Convert this to a tree where value of each node will be the sum of the values of all the nodes in left and right sub trees of the original tree. The values of leaf nodes are changed to 0.
Note: You have to modify the given tree in-place.
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
Example 2:
Input:
            10
        /        \
      -2           6
     /   \        /  \
    8    -4      7     5
    / \   / \    / \   / \
  2  -2 3  -5  9  -8 2   8
Output:
            29
        /        \
       2          23
     /  \        /  \
    0   -2      1    10
   / \  / \    / \   / \
   0  0 0   0  0   0 0   0
Explanation:
                 (-2+6+8-4+7+5+2-2+3-5+9-8+2+8)
               /                                \
          (8-4+2-2+3-5)                    (7+5+9-8+2+8)
          /      \                            /      \       
       (2-2)   (3-5)                        (9-8)    (2+8)
        /     \  /    \                      /     \   /     \
       0      0 0      0                   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 is None:
			return 0
		result = root.data
		left_value = self.toSumTree(root.left)
		right_value = self.toSumTree(root.right)
		root.data = left_value + right_value
		return root.data + result


class Solution:

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


class Solution:

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


class Solution:

	def toSumTree(self, root):

		def f(root):
			if not root:
				return 0
			if not root.left and (not root.right):
				tmp = root.data
				root.data = 0
				return tmp
			else:
				tmp = root.data
				root.data = f(root.left) + f(root.right)
				return root.data + tmp
		f(root)
		return root


class Solution:

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


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 root.data + old
		return dfs(root)


class Solution:

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


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):
		return self._toSumTree(root)

	def _toSumTree(self, node):
		if node:
			node.data = self.sum(node.left) + self.sum(node.right)
			self._toSumTree(node.left)
			self._toSumTree(node.right)

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


class Solution:

	def toSumTree(self, root):

		def rec(root):
			if not root:
				return 0
			t = root.data
			root.data = rec(root.left) + rec(root.right)
			return t + root.data
		rec(root)


class Solution:

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

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


class Solution:

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

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


class Solution:

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


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 fun(root):
			if not root:
				return 0
			elif not root.left and (not root.right):
				k = root.data
				root.data = 0
				return k
			else:
				left = fun(root.left)
				right = fun(root.right)
				k = root.data
				m = left + right
				root.data = m
				return m + k
		fun(root)


class Solution:

	def toSumTree(self, root):

		def backtracking(root):
			if not root:
				return 0
			max_left = backtracking(root.left)
			max_right = backtracking(root.right)
			temp = root.data
			root.data = max_left + max_right
			return root.data + temp
		backtracking(root)
		return root


class Solution:

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


class Solution:

	def toSumTree(self, root):
		if root.left is None and root.right is None:
			return 0

		def findsum(root):
			if root is None:
				return 0
			old_value = root.data
			left = findsum(root.left)
			right = findsum(root.right)
			root.data = left + right
			return old_value + root.data
		a = 0
		b = 0
		if root.left:
			a = findsum(root.left)
		if root.right:
			b = findsum(root.right)
		root.data = a + b
		return root


class Solution:

	def toSumTree(self, root):

		def travers(root):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				q = root.data
				root.data = 0
				return q
			z = root.data
			root.data = travers(root.left) + travers(root.right)
			return root.data + z
		return travers(root)


class Solution:

	def toSumTree(self, root):

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


class Solution:

	def toSumTree(self, root):

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


class Solution:

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

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


class Solution:

	def toSumTreeCalc(self, root):
		if root == None:
			return 0
		myNum = root.data
		mySum = 0
		if root.left != None:
			mySum += self.toSumTreeCalc(root.left)
		if root.right != None:
			mySum += self.toSumTreeCalc(root.right)
		root.data = mySum
		return myNum + mySum

	def toSumTree(self, root):
		self.toSumTreeCalc(root)
		return 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 Solution:

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


class Solution:

	def toSumTree(self, root):

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


class Solution:

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

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


class Solution:

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

	def toSumTree(self, root):
		q = []
		q.append(root)
		while len(q):
			p = q.pop(0)
			s = 0
			if p.left:
				s = s + self.summing(p.left)
				q.append(p.left)
			if p.right:
				s = s + self.summing(p.right)
				q.append(p.right)
			p.data = s


class Solution:

	def toSumTree(self, root):

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


class Solution:

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


class Solution:

	def toSumTree(self, root):

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


class Solution:

	def solve(self, root):
		if not root:
			return 0
		l = self.solve(root.left)
		r = self.solve(root.right)
		t = root.data + l + r
		root.data = l + r
		return t

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


class Solution:

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


class Solution:

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

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


class Solution:

	def toSumTreeHelper(self, root):
		if root == None:
			return (0, 0)
		(leftOldData, leftNewData) = self.toSumTreeHelper(root.left)
		(rightOldData, rightNewData) = self.toSumTreeHelper(root.right)
		oldData = root.data
		root.data = leftOldData + rightOldData + leftNewData + rightNewData
		newData = root.data
		return (oldData, newData)

	def toSumTree(self, root):
		(oldData, newData) = self.toSumTreeHelper(root)
		return


class Solution:

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


class Solution:

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

	def s(self, r):
		if r is None:
			return 0
		oldvalue = r.data
		r.data = self.s(r.left) + self.s(r.right)
		return oldvalue + r.data


class Solution:

	def toSumTree(self, root):

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


class Solution:

	def tree(self, root):
		(left, right) = (root.left, root.right)
		if left == None and right == None:
			temp = root.data
			root.data = 0
			return temp
		else:
			(a, b, c) = (0, 0, root.data)
			if left != None:
				a = self.tree(left)
			if right != None:
				b = self.tree(right)
			root.data = a + b
		return root.data + c

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


class Solution:

	def toSumTree(self, root):
		leftData = rightData = leftSumTree = rightSumTree = 0
		if root.left is not None:
			leftData = root.left.data
			self.toSumTree(root.left)
			leftSumTree = root.left.data
		if root.right is not None:
			rightData = root.right.data
			self.toSumTree(root.right)
			rightSumTree = root.right.data
		if leftData == rightData == 0:
			root.data = 0
		else:
			root.data = leftData + rightData + leftSumTree + rightSumTree


class Solution:

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


class Solution:

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

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


class Solution:

	def toSumTree(self, root):

		def summ(x):
			if x == None:
				return 0
			pre = x.data
			le = summ(x.left)
			rt = summ(x.right)
			x.data = le + rt
			return x.data + pre
		summ(root)


class Solution:

	def toSumTree(self, root):
		Solution.mutate(root)

	@staticmethod
	def mutate(node):
		if node is None:
			return 0
		temp = node.data
		temp += Solution.mutate(node.left)
		temp += Solution.mutate(node.right)
		node.data = temp - node.data
		return temp


class Solution:

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


class Solution:

	def rec(self, node):
		if not node:
			return 0
		r = self.rec(node.right)
		l = self.rec(node.left)
		cur = node.data
		node.data = r + l
		return cur + node.data

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


class Solution:

	def _backtrack(self, node):
		if not node:
			return 0
		ret_val = node.data
		node.data = self._backtrack(node.left) + self._backtrack(node.right)
		return ret_val + node.data

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


class Solution:

	def toSumTree(self, root):
		transformTree(root, 0)
		return root

def transformTree(root, sum):
	if not root:
		return 0
	oldValue = root.data
	leftSum = transformTree(root.left, sum)
	rightSum = transformTree(root.right, sum)
	root.data = leftSum + rightSum
	return leftSum + rightSum + oldValue


class Solution:

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


class Solution:

	def toSumTree(self, root):

		def l(root):
			if not root:
				return 0
			if not root.left and (not root.right):
				temp = root.data
				root.data = 0
				return temp
			val = l(root.left)
			var = l(root.right)
			ans = root.data + val + var
			root.data = val + var
			return ans
		return l(root)


class Solution:

	def sumAll(self, root):
		if not root:
			return 0
		l = self.sumAll(root.left)
		r = self.sumAll(root.right)
		summ = root.data
		root.data = l + r
		return summ + root.data

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


class Solution:

	def toSumTree(self, root):

		def helper(root):
			if not root:
				return 0
			left = helper(root.left)
			right = helper(root.right)
			tmp = root.data
			root.data = left + right
			return tmp + left + right
		helper(root)


class Solution:

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

	def traverse_sum(self, root):
		left_sub = 0
		right_sub = 0
		if root.left != None:
			left_sub = root.left.data + self.traverse_sum(root.left)
		if root.right != None:
			right_sub = root.right.data + self.traverse_sum(root.right)
		root.data = left_sub + right_sub
		return root.data


class Solution:

	def toSumTree(self, node):
		self.postorder(root, [0])

	def postorder(self, root, temp):
		if root == None:
			return temp[0]
		self.postorder(root.left, temp)
		r = self.postorder(root.right, [0])
		temp[0] += root.data + r
		root.data = temp[0] - root.data
		return temp[0]


class Solution:

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