Given a binary tree with N nodes, in which each node value represents number of candies present at that node. In one move, one may choose two adjacent nodes and move one candy from one node to another (the move may be from parent to child, or from child to parent.) 
The task is to find the number of moves required such that every node have exactly one candy.
Example 1:
Input :      3
           /   \
          0     0 
Output : 2
Explanation: 
From the root of the tree, we move one 
candy to its left child, and one candy to
its right child.
Example 2:
Input :      0
           /   \
          3     0  
Output : 3
Explanation : 
From the left child of the root, we move 
two candies to the root [taking two moves]. 
Then, we move one candy from the root of the 
tree to the right child.
Your task :
You don't have to read input or print anything. Your task is to complete the function distributeCandy() which takes the root of the tree as input and returns the number of moves required such that every node has exactly one candy.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(h)
 
Constraints:
1<=n<=10^4

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''



class Solution:

    def distributeCandy(self, root):

        #code here

Solutions:
class Solution:

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

	def distributeCandy(self, root):
		self.ans = 0
		self.solve(root)
		return self.ans


class Solution:

	def travel(root, move):
		if root is None:
			return 0
		left = Solution.travel(root.left, move)
		right = Solution.travel(root.right, move)
		move[0] += abs(right) + abs(left)
		if root.data + right + left == 1:
			return 0
		return root.data + left + right - 1

	def distributeCandy(self, root):
		move = [0]
		Solution.travel(root, move)
		return move[0]


class Solution:

	def distributeCandy(self, root):

		def f(node, ans):
			if not node:
				return 0
			l = f(node.left, ans)
			r = f(node.right, ans)
			temp = l + r + node.data - 1
			ans[0] += abs(l) + abs(r)
			return temp
		ans = [0]
		f(root, ans)
		return ans[0]


def solve(curr, moves):
	if curr == None:
		return 0
	l = solve(curr.left, moves)
	r = solve(curr.right, moves)
	moves[0] = moves[0] + max(l, -l) + max(r, -r)
	return l + r + curr.data - 1

class Solution:

	def distributeCandy(self, root):
		moves = [0]
		solve(root, moves)
		return moves[0]


class Solution:

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

	def distributeCandy(self, root):
		ans = 0
		(tmp, ans) = self.recursive_func(root, ans)
		return ans


class Solution:

	def find(self, root, ans):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return root.data
		left_val = self.find(root.left, ans)
		right_val = self.find(root.right, ans)
		if root.left:
			ans[0] += abs(left_val - 1)
			root.data += left_val - 1
		if root.right:
			ans[0] += abs(right_val - 1)
			root.data += right_val - 1
		return root.data

	def distributeCandy(self, root):
		ans = [0]
		self.find(root, ans)
		return ans[0]


class Solution:

	def distributeCandy(self, root):
		ans = [0]

		def helper(x):
			if not x:
				return 0
			l = helper(x.left)
			r = helper(x.right)
			ans[0] = ans[0] + abs(l) + abs(r)
			return x.data + l + r - 1
		helper(root)
		return ans[0]


class Solution:
	ans = 0

	def distributeCandyUtil(self, root):
		if root is None:
			return
		self.distributeCandyUtil(root.left)
		self.distributeCandyUtil(root.right)
		if root.left is not None and root.left.data != 1:
			if root.left.data < 1:
				takeFromParent = 1 - root.left.data
				root.data -= takeFromParent
				root.left.data += takeFromParent
				self.ans += takeFromParent
			else:
				putToParent = root.left.data - 1
				root.data += putToParent
				root.left.data -= putToParent
				self.ans += putToParent
		if root.right is not None and root.right.data != 1:
			if root.right.data < 1:
				takeFromParent = 1 - root.right.data
				root.data -= takeFromParent
				root.right.data += takeFromParent
				self.ans += takeFromParent
			else:
				putToParent = root.right.data - 1
				root.data += putToParent
				root.right.data -= putToParent
				self.ans += putToParent

	def distributeCandy(self, root):
		self.distributeCandyUtil(root)
		return self.ans


class Solution:

	def distributeCandy(self, root):
		ans = [0]

		def rec(nod):
			if nod is None:
				return 0
			l = rec(nod.left)
			r = rec(nod.right)
			ans[0] += abs(l) + abs(r)
			return l + r - 1 + nod.data
		rec(root)
		return ans[0]


class Solution:

	def distributeCandy(self, root):

		def solve(root, c):
			if not root:
				return 0
			l = solve(root.left, c)
			r = solve(root.right, c)
			c[0] += abs(l) + abs(r)
			return root.data + l + r - 1
		c = [0]
		solve(root, c)
		return c[0]


class Solution:

	def distributeCandy(self, root):
		global ans
		ans = 0

		def rec(r):
			global ans
			if not r:
				return 0
			left = rec(r.left)
			right = rec(r.right)
			ans += abs(left) + abs(right)
			return left + right + r.data - 1
		rec(root)
		return ans


class Solution:

	def distributeCandy(self, root):

		def ok(root, steps):
			if not root:
				return (0, steps)
			(l, steps) = ok(root.left, steps)
			(r, steps) = ok(root.right, steps)
			steps += abs(l) + abs(r)
			return (l + r + root.data - 1, steps)
		steps = 0
		return ok(root, 0)[1]


class Solution:

	def distributeCandy(self, root):
		count = [0]

		def solve(root):
			if root is None:
				return 0
			l = solve(root.left)
			r = solve(root.right)
			count[0] += abs(l) + abs(r)
			return root.data + l + r - 1
		solve(root)
		return count[0]


class Solution:

	def travel(root, move):
		if root is None:
			return 0
		left = Solution.travel(root.left, move)
		right = Solution.travel(root.right, move)
		move[0] += abs(right) + abs(left)
		if root.data + right + left == 1:
			return 0
		return root.data + left + right - 1

	def distributeCandy(self, root):
		move = [0]
		Solution.travel(root, move)
		return move[0]
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = 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()
		print(ob.distributeCandy(root))


class Solution:

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

		def rec(i):
			if i == None:
				return 0
			left = rec(i.left)
			right = rec(i.right)
			self.ans += abs(i.data - 1 + left + right)
			return i.data - 1 + left + right
		left = rec(root.left)
		right = rec(root.right)
		return self.ans


class Solution:

	def distributeCandy(self, root):
		ans = [0]

		def solve(root):
			a = b = 0
			if root.left:
				a = solve(root.left)
			if root.right:
				b = solve(root.right)
			ans[0] += abs(a) + abs(b)
			return root.data + a + b - 1
		solve(root)
		return ans[0]


class Solution:

	def distributeCandy(self, r):
		self.ans = 0

		def ss(node):
			if not node:
				return 0
			l = ss(node.left)
			r = ss(node.right)
			self.ans += abs(l) + abs(r)
			return l + r + node.data - 1
		ss(r)
		return self.ans


class Solution:

	def distributeCandy(self, root):
		val = [0]

		def isOk(root, val):
			if not root:
				return 0
			if not root.left and (not root.right):
				return root.data - 1
			left = isOk(root.left, val)
			right = isOk(root.right, val)
			new = root.data - 1 + left + right
			val[0] += abs(left) + abs(right)
			return new
		isOk(root, val)
		return val[0]


class Solution:

	def distributeCandy(self, root):
		self.moves = 0

		def dfs(root):
			if not root:
				return 0
			left = dfs(root.left)
			right = dfs(root.right)
			self.moves += abs(left) + abs(right)
			return left + right + root.data - 1
		dfs(root)
		return self.moves


class Solution:

	def distributeCandy(self, root):
		if not root:
			return 0
		ans = 0

		def moves(node):
			nonlocal ans
			if not node:
				return 0
			left = moves(node.left)
			right = moves(node.right)
			ans += abs(left) + abs(right)
			if node.data + left + right > 1 or node.data + left + right < 1:
				return node.data + left + right - 1
			if node.data + left + right == 1:
				return 0
		moves(root)
		return ans


class Solution:

	def distributeCandy(self, root):
		ans = 0

		def f(root):
			if not root:
				return 0
			nonlocal ans
			a = f(root.left)
			b = f(root.right)
			ans += abs(a) + abs(b)
			return root.data + a + b - 1
		f(root)
		return ans


def givecandies(node, numm):
	if node == None:
		return 0
	left = givecandies(node.left, numm)
	right = givecandies(node.right, numm)
	numm[0] += abs(left) + abs(right)
	return node.data + left + right - 1

class Solution:

	def distributeCandy(self, root):
		numm = [0]
		givecandies(root, numm)
		return numm[0]


class Solution:

	def distributeCandy(self, root):
		move = 0

		def jump_node(root, ans):
			if root == None:
				k = [0, ans]
				return k
			(l, ans) = jump_node(root.left, ans)
			(r, ans) = jump_node(root.right, ans)
			ans += abs(l) + abs(r)
			k = [root.data + l + r - 1, ans]
			return k
		(z, move) = jump_node(root, move)
		return move


class Solution:

	def node_type(self, r):
		if r.right == None and r.left == None:
			return 'Leaf'
		elif r.right == None:
			return 'Left'
		elif r.left == None:
			return 'Right'
		else:
			return 'Both'

	def nodeval(self, r):
		if self.node_type(r) == 'Leaf':
			return 1 - r.data
		elif self.node_type(r) == 'Left':
			return 1 - r.data + self.nodeval(r.left)
		elif self.node_type(r) == 'Right':
			return 1 - r.data + self.nodeval(r.right)
		else:
			return 1 - r.data + self.nodeval(r.right) + self.nodeval(r.left)

	def helper(self, r, sm):
		if self.node_type(r) == 'Leaf':
			return 0
		elif self.node_type(r) == 'Both':
			L_Candies = self.nodeval(r.left)
			R_Candies = sm - L_Candies - (1 - r.data)
			return abs(L_Candies) + abs(R_Candies) + self.helper(r.left, L_Candies) + self.helper(r.right, R_Candies)
		elif self.node_type(r) == 'Left':
			L_Candies = sm - (1 - r.data)
			return abs(L_Candies) + self.helper(r.left, L_Candies)
		else:
			R_Candies = sm - (1 - r.data)
			return abs(R_Candies) + self.helper(r.right, R_Candies)

	def distributeCandy(self, r):
		return self.helper(r, self.nodeval(r))


class Solution:

	def __init__(self):
		self.moves = 0

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

	def distributeCandy(self, root):
		self.cand_dist(root)
		return self.moves


class Solution:

	def distributeCandy(self, root):
		moves = [0]
		distribute(root, moves)
		return moves[0]

def distribute(cur, moves):
	if not cur:
		return 0
	left_delta = distribute(cur.left, moves)
	right_delta = distribute(cur.right, moves)
	moves[0] += abs(left_delta) + abs(right_delta)
	return cur.data + left_delta + right_delta - 1