Given a binary tree of size N+1, your task is to complete the function tiltTree(), that return the tilt of the whole tree. The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null nodes are assigned tilt to be zero. Therefore, tilt of the whole tree is defined as the sum of all nodes’ tilt.
Examples 1:
Input: 
       1
      / \
     2   3
Output: 1
Explanation:
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1
Example 2:
Input:
        4 
       / \
      2   9 
     / \   \
    3   5   7 
Output: 15 
Explanation:
Tilt of node 3 : 0 
Tilt of node 5 : 0 
Tilt of node 7 : 0
Tilt of node 2 : |3-5| = 2 
Tilt of node 9 : |0-7| = 7 
Tilt of node 4 : |(3+5+2)-(9+7)| = 6 
Tilt of binary tree : 0 + 0 + 0 + 2 + 7 + 6 = 15
Your Task:
You don't need to read input or print anything. Your task is to complete the function tiltTree() which takes root node of the tree as input parameter and returns an integer denoting the tilt of the tree. If the tree is empty, return 0. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1<=T<=100
0<=N<=500

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

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

class Solution:
    def tiltTree(self,root):
        #code here

Solutions:
class Solution:

	def fun(self, root, s, res):
		if root == None:
			return 0
		l = self.fun(root.left, s, res)
		r = self.fun(root.right, s, res)
		s[0] = l + root.data + r
		root.data = abs(l - r)
		res[0] += root.data
		return s[0]

	def tiltTree(self, root):
		(s, res) = ([0], [0])
		self.fun(root, s, res)
		return res[0]


class Solution:

	def tiltTree(self, root):
		global tilt
		tilt = 0
		self.tiltu(root)
		return tilt

	def tiltu(self, root):
		global tilt
		if not root:
			return 0
		(ln, rn) = (root.left, root.right)
		rs = ls = 0
		if ln:
			ls = self.tiltu(ln)
		if rn:
			rs = self.tiltu(rn)
		if not ln and (not rn):
			return root.data
		tilt += abs(rs - ls)
		return rs + ls + root.data


class Queue:

	def __init__(self):
		self.l = []

	def __str__(self):
		values = []
		values = [str(x) for x in self.l]
		return ' '.join(values)

	def isEmpty(self):
		if self.l == []:
			return True
		else:
			return False

	def Enqueue(self, val):
		self.l.append(val)
		return 'Insertion is completed'

	def Dequeue(self):
		if self.isEmpty():
			return 'Queue is empty'
		else:
			return self.l.pop(0)

def leveltrav(Node):
	l = []
	if not Node:
		return
	else:
		customQueue = Queue()
		customQueue.Enqueue(Node)
		while not customQueue.isEmpty():
			root = customQueue.Dequeue()
			l.append(root)
			if root.left is not None:
				customQueue.Enqueue(root.left)
			if root.right is not None:
				customQueue.Enqueue(root.right)
		return l

class Solution:

	def tiltTree(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 0
		a = leveltrav(root)
		l = []
		l1 = []
		for i in a:
			a1 = [0]
			a2 = [0]
			if i.left:
				a1 = self.helper(i.left, l)
				l = []
			if i.right:
				a2 = self.helper(i.right, l)
				l = []
			l1.append(abs(sum(a1) - sum(a2)))
		return sum(l1)

	def helper(self, root, l):
		if not root:
			return
		else:
			if root.left:
				self.helper(root.left, l)
			l.append(root.data)
			if root.right:
				self.helper(root.right, l)
		return l


class Solution:

	def tiltTree(self, root):

		def sol1(root1):
			if not root1:
				return 0
			else:
				left = sol1(root1.left)
				right = sol1(root1.right)
				return right + left + root1.data
		global s, sum1
		s = 0
		sum1 = 0

		def sol(root):
			global s
			if not root:
				return 0
			if root:
				left = sol1(root.left)
				right = sol1(root.right)
				s = s + abs(left - right)
				sol(root.left)
				sol(root.right)
				return s
		k = sol(root)
		return k


class Solution:

	def tiltTree(self, root):
		self.s = 0

		def help(root):
			if not root:
				return 0
			l = help(root.left)
			r = help(root.right)
			self.s += abs(r - l)
			return l + root.data + r
		help(root)
		return self.s


class Solution:

	def tiltTree(self, root):
		self.tilt = 0

		def helper(node):
			if node == None:
				return 0
			lSum = helper(node.left)
			rSum = helper(node.right)
			localTilt = abs(lSum - rSum)
			self.tilt += localTilt
			localSum = lSum + rSum + node.data
			return localSum
		helper(root)
		return self.tilt


class Solution:

	def tiltTree(self, root):
		A = []
		self.x(root, A)
		return sum(A)

	def x(self, root, A):
		if root.left is not None:
			self.x(root.left, A)
		if root.right is not None:
			self.x(root.right, A)
		if root.left is None:
			l = 0
		else:
			l = root.left.data
		if root.right is None:
			r = 0
		else:
			r = root.right.data
		A.append(abs(l - r))
		root.data += l + r


class Solution:

	def getTilt(self, root, tilt):
		if not root:
			return 0
		l = self.getTilt(root.left, tilt)
		r = self.getTilt(root.right, tilt)
		tilt[0] = tilt[0] + abs(l - r)
		return l + r + root.data

	def tiltTree(self, root):
		tilt = [0]
		x = self.getTilt(root, tilt)
		return tilt[0]


class Solution:

	def __init__(self):
		self.sum = 0

	def tiltTree(self, root):
		l = self.solve(root.left)
		r = self.solve(root.right)
		return self.sum + abs(l - r)

	def solve(self, root):
		if root == None:
			return 0
		l = self.solve(root.left)
		r = self.solve(root.right)
		self.sum += abs(l - r)
		return root.data + l + r


class Solution:
	sum_var = 0

	def recur(self, root):
		if root == None:
			return 0
		lh = self.recur(root.left)
		rh = self.recur(root.right)
		self.sum_var += abs(lh - rh)
		return lh + rh + root.data

	def tiltTree(self, root):
		self.recur(root)
		return self.sum_var


class Solution:

	def tiltTree(self, root):
		tiltSum = 0

		def subtreeSum(node):
			nonlocal tiltSum
			if node == None:
				return 0
			leftSubSum = subtreeSum(node.left)
			rightSubSum = subtreeSum(node.right)
			tiltSum += abs(rightSubSum - leftSubSum)
			return leftSubSum + rightSubSum + node.data
		subtreeSum(root)
		return tiltSum


class Solution:

	def tiltTree(self, root):
		self.tilt = 0
		self.dfs(root, 1)
		return self.tilt

	def dfs(self, root, level):
		if not root:
			return 0
		l = self.dfs(root.left, level + 1)
		r = self.dfs(root.right, level + 1)
		self.tilt += abs(l - r)
		return l + r + root.data


class Solution:

	def dfs(self, root):
		if not root:
			return 0
		ls = self.dfs(root.left)
		rs = self.dfs(root.right)
		self.tilt += abs(rs - ls)
		return rs + ls + root.data

	def tiltTree(self, root):
		self.tilt = 0
		self.dfs(root)
		return self.tilt


class Solution:

	def tiltTree(self, root):
		return self.tiltBranch(root)[1]

	def tiltBranch(self, root):
		if not root:
			return (0, 0)
		(left_sum, left_result) = self.tiltBranch(root.left)
		(right_sum, right_result) = self.tiltBranch(root.right)
		summa = root.data + left_sum + right_sum
		result = abs(left_sum - right_sum) + left_result + right_result
		return (summa, result)


class Solution:
	ans = 0

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

	def tiltTree(self, root):
		self.solve(root)
		return self.ans


def traverse(root, tilt):
	if not root:
		return 0
	left = traverse(root.left, tilt)
	right = traverse(root.right, tilt)
	tilt[0] += abs(left - right)
	return left + right + root.data

def Tilt(root):
	tilt = [0]
	traverse(root, tilt)
	return tilt[0]

class Solution:

	def tiltTree(self, root):
		return Tilt(root)


class Solution:

	def tiltTree(self, root):

		def dfs(root, tilt):
			if root is None:
				return 0
			l = dfs(root.left, tilt)
			r = dfs(root.right, tilt)
			tilt[0] += abs(l - r)
			return l + r + root.data
		tilt = [0]
		dfs(root, tilt)
		return tilt[0]


class Solution:

	def tiltTree(self, root):

		def traversal(root):
			nonlocal total
			if root == None:
				return 0
			ls = traversal(root.left)
			rs = traversal(root.right)
			sum1 = ls + rs + root.data
			total += abs(ls - rs)
			return sum1
		total = 0
		traversal(root)
		return total


class Solution:

	def tilt(self, root):
		if root == None:
			return (0, 0)
		(leftSum, lefttilt) = self.tilt(root.left)
		(rightSum, righttilt) = self.tilt(root.right)
		add = leftSum + rightSum + root.data
		t = abs(leftSum - rightSum) + lefttilt + righttilt
		return (add, t)

	def tiltTree(self, root):
		(add, t) = self.tilt(root)
		return t


class Solution:

	def tiltTree(self, root):

		def dump(root, ans):
			if not root:
				return 0
			l_sum = dump(root.left, ans)
			r_sum = dump(root.right, ans)
			ans[0] += abs(l_sum - r_sum)
			return l_sum + r_sum + root.data
		ans = [0]
		dump(root, ans)
		return ans[0]


class Solution:

	def dump(self, root, ans):
		if root == None:
			return 0
		left = self.dump(root.left, ans)
		right = self.dump(root.right, ans)
		ans[0] += abs(left - right)
		return left + right + root.data

	def tiltTree(self, root):
		ans = [0]
		self.dump(root, ans)
		return ans[0]


class Solution:

	def solve(self, root, arr):
		if root == None:
			return 0
		a = self.solve(root.left, arr)
		b = self.solve(root.right, arr)
		arr[0] += max(a, b) - min(a, b)
		return a + b + root.data

	def tiltTree(self, root):
		arr = [0]
		self.solve(root, arr)
		return arr[0]


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

class Solution:

	def tiltTree(self, root):
		if root == None:
			return 0
		l_tilt = self.tiltTree(root.left)
		r_tilt = self.tiltTree(root.right)
		tilt = 0
		if root.left:
			tilt = sum(root.left)
		if root.right:
			tilt = abs(tilt - sum(root.right))
		return tilt + l_tilt + r_tilt
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.tiltTree(root)
		print(res)


class Solution:

	def tiltTree(self, root):
		self.ans = 0

		def dfs(root):
			if not root:
				return 0
			leftsum = dfs(root.left)
			rightsum = dfs(root.right)
			currtilt = abs(leftsum - rightsum)
			self.ans += currtilt
			return leftsum + rightsum + root.data
		dfs(root)
		return self.ans


class Solution:

	def tiltTree(self, root):
		if root == None:
			return 0
		t = abs(self.sum(root.left) - self.sum(root.right))
		tilt = t + self.tiltTree(root.left) + self.tiltTree(root.right)
		return tilt

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


class Solution:

	def solve(self, root, b):
		if root is None:
			return 0
		if root.left is not None:
			l = self.solve(root.left, b)
		else:
			l = 0
		if root.right is not None:
			r = self.solve(root.right, b)
		else:
			r = 0
		b[0] = b[0] + abs(l - r)
		return l + r + root.data

	def tiltTree(self, root):
		b = [0]
		self.solve(root, b)
		return b[0]


from collections import defaultdict

def leftnodes(root, left):
	if not root:
		return
	left.append(root.data)
	leftnodes(root.left, left)
	leftnodes(root.right, left)

def rightnodes(root, right):
	if not root:
		return
	rightnodes(root.right, right)
	rightnodes(root.left, right)
	right.append(root.data)

class Solution:

	def tiltTree(self, root):
		ans = defaultdict(list)

		def traverse(root):
			left = []
			leftnodes(root.left, left)
			if root.left:
				traverse(root.left)
			if root.right:
				traverse(root.right)
			if root.right or root.left:
				ans[root.data].append(sum(left))
		traverse(root)

		def traverse2(root):
			right = []
			rightnodes(root.right, right)
			if root.left:
				traverse2(root.left)
			if root.right:
				traverse2(root.right)
			if root.right or root.left:
				ans[root.data].append(sum(right))
		traverse2(root)
		total = 0
		for (key, value) in ans.items():
			total += abs(value[0] - value[1])
		return total


class Solution:

	def recur(self, root, ans):
		if not root:
			return 0
		left = self.recur(root.left, ans)
		right = self.recur(root.right, ans)
		ans[0] += abs(left - right)
		return left + right + root.data

	def tiltTree(self, root):
		ans = [0]
		self.recur(root, ans)
		return ans[0]


class Solution:

	def soln(self, root, total):
		if root is None:
			return 0
		l = self.soln(root.left, self.total)
		r = self.soln(root.right, self.total)
		self.total += abs(l - r)
		return l + r + root.data

	def tiltTree(self, root):
		if root is None:
			return 0
		self.total = 0
		self.soln(root, self.total)
		return self.total


class Solution:

	def __init__(self):
		self.tilt = 0

	def helper(self, root, d):
		if root is None:
			return 0
		if root in d:
			return d[root]
		leftSum = self.helper(root.left, d)
		rightSum = self.helper(root.right, d)
		res = root.data + leftSum + rightSum
		d[root] = res
		self.tilt += abs(rightSum - leftSum)
		return res

	def tiltTree(self, root):
		d = {}
		self.helper(root, d)
		return self.tilt


class Solution:

	def tiltTree(self, root):
		tilt = [0]
		self.computetilt(root, tilt)
		return tilt[0]

	def computetilt(self, root, tilt):
		if root == None:
			return 0
		left = self.computetilt(root.left, tilt)
		right = self.computetilt(root.right, tilt)
		tilt[0] += abs(left - right)
		return left + right + root.data


class Solution:

	def tiltOfTree(self, node, tilt):
		if node is None:
			return 0
		ls = self.tiltOfTree(node.left, tilt)
		rs = self.tiltOfTree(node.right, tilt)
		tilt[0] += abs(ls - rs)
		return ls + rs + node.data

	def tiltTree(self, root):
		tilt = [0]
		self.tiltOfTree(root, tilt)
		return tilt[0]


class Solution:

	def sum_root(self, root, store):
		if root is None:
			return 0
		left = self.sum_root(root.left, store)
		right = self.sum_root(root.right, store)
		store[0] += abs(left - right)
		return left + right + root.data

	def tiltTree(self, root):
		store = [0]
		self.sum_root(root, store)
		return store[0]


class Solution:

	def tiltTree(self, root):
		a = [0]
		tiltTreeUtil(root, a)
		return a[0]

def tiltTreeUtil(root, a):
	if root == None:
		return 0
	else:
		l = tiltTreeUtil(root.left, a)
		r = tiltTreeUtil(root.right, a)
		a[0] += abs(l - r)
		return l + r + root.data


class Solution:

	def tiltTree(self, root):
		return self.get(root, {})

	def get(self, root, d):
		if root:
			return abs(self.sumTree(root.left, d) - self.sumTree(root.right, d)) + self.get(root.left, d) + self.get(root.right, d)
		return 0

	def sumTree(self, root, d):
		if root in d:
			return d[root]
		elif root:
			d[root] = root.data + self.sumTree(root.left, d) + self.sumTree(root.right, d)
			return d[root]
		else:
			return 0


class Solution:

	def tiltTree(self, root):

		def solve(root):
			if root == None:
				return {'tilt': 0, 'sum': 0}
			left = solve(root.left)
			right = solve(root.right)
			curtilt = abs(left['sum'] - right['sum'])
			totaltilt = left['tilt'] + right['tilt'] + curtilt
			total = left['sum'] + right['sum'] + root.data
			return {'tilt': totaltilt, 'sum': total}
		return solve(root)['tilt']


class Solution:

	def tiltTree(self, root):
		tilt = [0]
		self.helper(root, tilt)
		return tilt[0]

	def helper(self, root, tilt):
		if root is None:
			return 0
		lsum = self.helper(root.left, tilt)
		rsum = self.helper(root.right, tilt)
		tilt[0] = tilt[0] + abs(lsum - rsum)
		return root.data + lsum + rsum


class Solution:

	def tiltTree(self, root):
		self.total_sm = 0

		def dfs(root):
			if root:
				l = dfs(root.left)
				r = dfs(root.right)
				sm = abs(l - r)
				self.total_sm += sm
				return l + r + root.data
			else:
				return 0
		dfs(root)
		return self.total_sm


class Solution:

	def __init__(self):
		self.ans = 0

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

	def tiltTree(self, root):
		self.tilt(root)
		return self.ans


class Solution:

	def __init__(self):
		self.tilt = 0

	def tiltTree(self, root):
		self.followUp(root)
		return self.tilt

	def followUp(self, root):
		if root is None:
			return 0
		left = self.followUp(root.left)
		right = self.followUp(root.right)
		self.tilt += abs(left - right)
		return root.data + left + right


def tilt(root, arr):
	if root == None:
		return 0
	else:
		l = tilt(root.left, arr)
		r = tilt(root.right, arr)
		arr[0] += abs(l - r)
		return l + r + root.data

class Solution:

	def tiltTree(self, root):
		arr = [0]
		tilt(root, arr)
		return arr[0]


class Solution:

	def tiltTree(self, root):

		def nodelist(root):
			nlist = []
			nlist.append(root)
			if root.left:
				nlist += nodelist(root.left)
			if root.right:
				nlist += nodelist(root.right)
			return nlist

		def nodesum(root):
			count = 0
			if root is None:
				return 0
			if root.left is None and root.right is None:
				count += 0
			if root.left is None and root.right:
				count += nodesum(root.right)
			if root.right is None and root.left:
				count += nodesum(root.left)
			if root.right and root.left:
				count += nodesum(root.right) + nodesum(root.left)
			count += root.data
			return count
		nodes = nodelist(root)
		tilt = 0
		for node in nodes:
			tilt += abs(nodesum(node.left) - nodesum(node.right))
		return tilt


class Solution:

	def tiltTree(self, root):

		def helper(root):
			if not root:
				return 0
			(lv, rv) = (helper(root.left), helper(root.right))
			self.ans += abs(lv - rv)
			return root.data + lv + rv
		self.ans = 0
		helper(root)
		return self.ans


class Solution:

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

	def tiltTree(self, root):
		sum = 0
		if root == None:
			return 0
		sum += abs(self.sumTree(root.left) - self.sumTree(root.right))
		l = self.tiltTree(root.left)
		r = self.tiltTree(root.right)
		return sum + l + r