Given a BST, transform it into greater sum tree where each node contains sum of all nodes greater than that node.
Example 1:
Input:
           2
         /    \
        1      6
              /  \
             3    7
Output: 18 16 13 7 0
Explanation:
Every node is replaced with the 
sum of nodes greater than itself. 
The resultant tree is:
               16
             /    \
           18       7
                  /   \
                 13    0
Example 2:
Input:
          2
         /
        1
Output: 2 0
Explanation:
The resultant tree is :
             0
            /
          2
Your task :
You don't have to read input or print anything. Your task is to complete the function transformTree() which takes the root of the tree as input and transforms the BST to a greater sum tree.
Note : The driver code prints the inorder traversal of the transformed BST.
 
Expected Time Complexity: O(N), N = number of nodes
Expected Auxiliary Space: O(N), N = number of nodes
 
Constraints :
1 ≤ N ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3



'''

# Tree Node

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

        

'''



class Solution:

    def transformTree(self, root):

        #code here



Solutions:
class Solution:

	def util(self, root):
		global v
		if root == None:
			return
		self.util(root.right)
		t = root.data
		root.data = v
		v += t
		self.util(root.left)

	def transformTree(self, root):
		global v
		v = 0
		self.util(root)
		return root


class Solution:

	def transformTree(self, root):

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			ino.append(root.data)
			inorder(root.right)
		ino = []
		inorder(root)
		prefixsum = []
		sum = 0
		for i in range(len(ino) - 1, -1, -1):
			prefixsum.append(sum)
			sum = sum + ino[i]
		prefixsum = prefixsum[::-1]
		g = {}
		for i in range(0, len(ino)):
			g[ino[i]] = prefixsum[i]

		def answer(root):
			if root == None:
				return
			answer(root.left)
			root.data = g[root.data]
			answer(root.right)
		answer(root)
		return root


class Solution:

	def transformTree(self, root):
		(count_, tempList) = ([0], self.inOrder(root))
		newTemp = [0] * len(tempList)
		for i in range(len(tempList) - 2, -1, -1):
			newTemp[i] = tempList[i + 1] + newTemp[i + 1]
		self.inOrderChng(root, newTemp, count_)

	def inOrderChng(self, root, arr, count):
		if root == None:
			return
		self.inOrderChng(root.left, arr, count)
		root.data = arr[count[0]]
		count[0] += 1
		self.inOrderChng(root.right, arr, count)

	def inOrder(self, root):
		if root == None:
			return []
		return self.inOrder(root.left) + [root.data] + self.inOrder(root.right)


class Solution:

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

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


class Solution:

	def transformTree(self, root):
		num = self.sum(root)
		return self._transform(root, [num])

	def _transform(self, node, num):
		if node:
			self._transform(node.left, num)
			(node.data, num[0]) = (num[0] - node.data, num[0] - node.data)
			self._transform(node.right, num)

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


class Solution:

	def transformTree(self, root):

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			res.append(root.data)
			inorder(root.right)
		res = []
		inorder(root)
		s = sum(res)
		for i in range(1, len(res)):
			res[i] += res[i - 1]

		def inorderchange(root):
			if root == None:
				return
			inorderchange(root.left)
			root.data = s - res[index[0]]
			index[0] += 1
			inorderchange(root.right)
		index = [0]
		inorderchange(root)
		return root


class Solution:

	def transformTree(self, root):
		(add, temp, stack) = (0, root, [root])
		d = {root: True}
		while stack:
			while stack[-1].right and stack[-1].right not in d:
				d[stack[-1].right] = True
				stack.append(stack[-1].right)
			a = stack.pop()
			(a.data, add) = (add, add + a.data)
			if a.left:
				stack.append(a.left)
		return root


class Solution:

	def transformTree(self, root):

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			res.append(root.data)
			inorder(root.right)

		def update(root):
			nonlocal j, gsm
			if not root:
				return
			update(root.left)
			root.data = gsm[j]
			j += 1
			update(root.right)
		res = []
		inorder(root)
		sm = sum(res)
		gsm = []
		it = 0
		for i in range(len(res)):
			it += res[i]
			gsm.append(sm - it)
		j = 0
		update(root)
		return root


class Solution:

	def helper(self, node):
		if node is None:
			return
		self.helper(node.right)
		temp = node.data
		node.data = self.data
		self.data += temp
		self.helper(node.left)

	def transformTree(self, root):
		self.data = 0
		self.helper(root)


class Solution:

	def transformTree(self, root):
		self.sum = 0

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


class Solution:

	def transformTree(self, root):

		def replace(root, top_sum):
			if root == None:
				return 0
			r = replace(root.right, top_sum)
			temp = root.data
			root.data = top_sum + r
			l = replace(root.left, r + temp + top_sum)
			return l + r + temp
		val = replace(root, 0)
		return root


class Solution:

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

	def transformTree(self, root):
		sum = [0]
		self.ReverseInorder(root, sum)
		return root


class Solution:

	def transformTree(self, root):

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

		def helper(root, sum):
			if not root:
				return sum
			sum = helper(root.left, sum) - root.data
			root.data = sum
			return helper(root.right, sum)
		helper(root, get_sum(root))


from collections import deque
import bisect

def bfs(node):
	(d, nodes) = (deque(), [])
	d.append(node)
	nodes.append(node.data)
	while d:
		n = d.popleft()
		if n.left:
			d.append(n.left)
			nodes.append(n.left.data)
		if n.right:
			d.append(n.right)
			nodes.append(n.right.data)
	return nodes

def dfs(root, ps, nodes):
	if root == None:
		return
	root.data = ps[-1] - ps[nodes[root.data]]
	dfs(root.left, ps, nodes)
	dfs(root.right, ps, nodes)

class Solution:

	def transformTree(self, root):
		nodes = bfs(root)
		(ps, l) = ([], nodes.copy())
		nodes.sort()
		a = 0
		d = {}
		s = set(nodes)
		nodes = list(s)
		nodes.sort()
		for i in nodes:
			a += i
			ps.append(a)
		for i in range(len(nodes)):
			d[nodes[i]] = i
		dfs(root, ps, d)


class Solution:

	def solve(self, root, q):
		if root is None:
			return
		self.solve(root.left, q)
		q.append(root.data)
		self.solve(root.right, q)

	def solve1(self, root, q):
		if root is None:
			return
		self.solve1(root.left, q)
		root.data = q[self.cnt]
		self.cnt += 1
		self.solve1(root.right, q)

	def transformTree(self, root):
		q = []
		self.solve(root, q)
		sm = 0
		temp = q[-1]
		q[-1] = 0
		for i in range(len(q) - 1):
			sm += temp
			temp = q[-i - 2]
			q[-i - 2] = sm
		self.cnt = 0
		self.solve1(root, q)


class Solution:
	Sum = 0

	def reversePreOrder(self, root):
		if root == None:
			return
		self.reversePreOrder(root.right)
		x = root.data
		root.data = self.Sum
		self.Sum += x
		self.reversePreOrder(root.left)
		return root

	def transformTree(self, root):
		return self.reversePreOrder(root)


class Solution:

	def transformTree(self, root):
		self.tot = 0
		self.tmp = 0

		def reverse_inorder(root):
			if root:
				reverse_inorder(root.right)
				self.tot += root.data
				root.data = self.tmp
				self.tmp = self.tot
				reverse_inorder(root.left)
		reverse_inorder(root)


class Solution:

	def transformTree(self, root):
		self.nums = 0

		def func(root):
			if root is None:
				return
			func(root.right)
			node = root.data
			root.data = self.nums
			self.nums += node
			func(root.left)
		func(root)
		return self.nums


class Solution:

	def transformTree(self, root, prev=0):
		if root is None:
			return 0
		sumR = self.transformTree(root.right, prev)
		temp = root.data
		root.data = sumR + prev
		prev += sumR + temp
		sumL = self.transformTree(root.left, prev)
		return sumL + temp + sumR


class Solution:

	def transformTree(self, root):

		def traversal(root):
			nonlocal sum1
			if root == None:
				return None
			if root.right:
				traversal(root.right)
			temp = root.data
			root.data = sum1
			sum1 += temp
			if root.left:
				traversal(root.left)
		sum1 = 0
		traversal(root)
		return root


import collections

class Solution:

	def transformTree(self, root):
		items = self.findItems(root)
		store = {}
		summa = 0
		for item in items:
			store[item] = summa
			summa += item
		tree = [root]
		while tree:
			head = tree.pop()
			if head is None:
				continue
			temp = head.data
			head.data = store[temp]
			tree.append(head.left)
			tree.append(head.right)
		return

	def findItems(self, root):
		if root is None:
			return []
		output = []
		output += self.findItems(root.right)
		output += [root.data]
		output += self.findItems(root.left)
		return output


class Solution:

	def inorder_ok(self, root, arr):
		if root:
			self.inorder_ok(root.left, arr)
			arr.append(root.data)
			self.inorder_ok(root.right, arr)

	def inorder(self, root, arr):
		if root:
			self.inorder(root.right, arr)
			root.data = arr.pop()
			self.inorder(root.left, arr)

	def transformTree(self, root):
		arr = list()
		self.inorder_ok(root, arr)
		temp = arr[-1]
		arr[-1] = 0
		for i in range(len(arr) - 2, -1, -1):
			temp2 = arr[i]
			arr[i] = arr[i + 1] + temp
			temp = temp2
		self.inorder(root, arr)
		return root


class Solution:

	def transformTree(self, root):
		self.k = 0

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


class Solution:

	def __init__(self):
		self.c = 0

	def check(self, a):
		if a:
			self.check(a.right)
			o = a.data
			a.data = self.c
			self.c += o
			self.check(a.left)

	def transformTree(self, root):
		self.check(root)
		return root


class Solution:
	sm = 0

	def transformTree(self, root):
		if not root:
			return
		if root.right:
			self.transformTree(root.right)
		curr = root.data
		root.data = self.sm
		self.sm += curr
		if root.left:
			self.transformTree(root.left)


class Solution:
	preSum = 0

	def transformTree(self, root):
		if root:
			self.transformTree(root.right)
			temp = root.data
			root.data = self.preSum
			self.preSum += temp
			self.transformTree(root.left)


import sys

class Solution:

	def transformTree(self, root):
		if not root:
			return root
		current = root
		tmp = 0
		successor = -sys.maxsize - 1
		while current:
			if current.right == None:
				if successor == -sys.maxsize - 1:
					successor = current.data
					current.data = 0
				else:
					tmp = current.data
					current.data = successor
					successor += tmp
				current = current.left
			else:
				right = current.right
				while right.left and right.left != current:
					right = right.left
				if not right.left:
					right.left = current
					current = current.right
				else:
					right.left = None
					tmp = current.data
					current.data = successor
					successor += tmp
					current = current.left


class Solution:

	def transformTree(self, root):
		global sm
		sm = 0
		self.updateValue(root)

	def updateValue(self, current):
		global sm
		if not current:
			return
		self.updateValue(current.right)
		temp = current.data
		current.data = sm
		sm += temp
		self.updateValue(current.left)


class Solution:

	def transformTree(self, root):

		def helper(root, val):
			if root is None:
				return val
			val = helper(root.right, val)
			k = root.data
			root.data = val
			val += k
			val = helper(root.left, val)
			return val
		helper(root, 0)
		return root


class Solution:

	def transformTree(self, root):
		self.presum = 0

		def afterOrder(node):
			if not node:
				return
			afterOrder(node.right)
			tmp = node.data
			node.data = self.presum
			self.presum += tmp
			afterOrder(node.left)
		afterOrder(root)
		return root


class Solution:

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

		def pos(r):
			if r:
				pos(r.right)
				p = r.data
				r.data = self.s
				self.s += p
				pos(r.left)
		pos(root)


class Solution:
	s = 0

	def solve(self, root):
		if root == None:
			return
		else:
			self.solve(root.right)
			self.s = self.s + root.data
			root.data = self.s - root.data
			self.solve(root.left)
		return root

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


class Solution:

	def inorder(self, root, l):
		if root == None:
			return []
		else:
			self.inorder(root.left, l)
			l.append(root.data)
			self.inorder(root.right, l)
		return l

	def solve(self, root, d):
		if root == None:
			return None
		else:
			root.data = d[root.data]
			l = self.solve(root.left, d)
			r = self.solve(root.right, d)
		return root

	def transformTree(self, root):
		l = []
		self.inorder(root, l)
		s = sum(l)
		d = {}
		for i in l:
			d[i] = d.get(i, 0) + (s - i)
			s = s - i
		return self.solve(root, d)


class Solution:

	def transformTree(self, root):
		ans = [0]
		head = None
		head = self.new(head, root)
		self.transformUtil(root, ans)
		return root

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

	def new(self, head, root):
		if root:
			head = Node(1)
			head.left = self.new(head.left, root.left)
			head.right = self.new(head.right, root.right)
			return head


class Solution:

	def transform_tree_util(self, root, s):
		if root is None:
			return
		self.transform_tree_util(root.right, s)
		temp = root.data
		root.data = s[0]
		s[0] += temp
		self.transform_tree_util(root.left, s)

	def transformTree(self, root):
		self.transform_tree_util(root, [0])


class Solution:

	def __init__(self):
		self.total = 0

	def inorder(self, root):
		if root.left != None:
			self.inorder(root.left)
		self.total += root.data
		if root.right != None:
			self.inorder(root.right)

	def setvalues(self, root):
		if root.left != None:
			self.setvalues(root.left)
		self.total -= root.data
		root.data = self.total
		if root.right != None:
			self.setvalues(root.right)

	def transformTree(self, root):
		self.inorder(root)
		self.setvalues(root)


class Solution:

	def transformTree(self, root):

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


class Solution:

	def dfs(self, root, nums):
		if not root:
			return
		self.dfs(root.left, nums)
		nums.append(root.data)
		self.dfs(root.right, nums)

	def transformTree(self, root):
		nums = []
		self.dfs(root, nums)
		total = sum(nums)

		def helper(root):
			nonlocal total
			if not root:
				return
			helper(root.left)
			total = total - root.data
			root.data = total
			helper(root.right)
		helper(root)
		return root


class Solution:

	def transformTree(self, root):
		if root is None:
			return None
		q = []
		cur = root
		temp = 0
		while True:
			if cur != None:
				q.append(cur)
				cur = cur.right
			elif q:
				cur = q.pop()
				j = cur.data
				cur.data = temp
				temp = temp + j
				cur = cur.left
			else:
				break
		return root


class Solution:

	def transformTree(self, root):
		self.t = 0

		def dfs(root):
			if root is None:
				return 0
			dfs(root.right)
			self.t = self.t + root.data
			root.data = self.t - root.data
			dfs(root.left)
		return dfs(root)


def in_Order(root):
	if not root:
		return []
	else:
		return in_Order(root.left) + [root] + in_Order(root.right)

class Solution:

	def transformTree(self, root):
		arr = in_Order(root)
		(tot, prev) = (0, 0)
		for i in range(len(arr) - 1, -1, -1):
			(tot, prev) = (tot + prev, arr[i].data)
			arr[i].data = tot


class Solution:

	def transformTree(self, root):

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


class Solution:

	def transformTree(self, root):

		def helper(root, a):
			if root is None:
				return a
			b = helper(root.right, a)
			c = root.data
			root.data = b
			d = helper(root.left, b + c)
			return d
		helper(root, 0)


class Solution:

	def transformTree(self, root):

		def inorder(root, arr):
			if not root:
				return
			else:
				inorder(root.left, arr)
				arr.append(root.data)
				inorder(root.right, arr)
				return arr
		arr = inorder(root, [])
		j = 0
		for i in range(len(arr) - 1, -1, -1):
			temp = arr[i]
			arr[i] = j
			j = j + temp

		def transform(root, arr, k):
			if not root:
				return
			else:
				transform(root.left, arr, k)
				root.data = arr[k[0]]
				k[0] = k[0] + 1
				transform(root.right, arr, k)
		transform(root, arr, [0])
		return root


class Solution:

	def transformTree(self, root):
		arr = []
		self.fillArr(root, arr)
		runningSum = 0
		for i in reversed(range(len(arr))):
			tmp = arr[i]
			arr[i] = runningSum
			runningSum += tmp
		self.setBST(root, arr, [0])

	def fillArr(self, root, arr):
		if root is None:
			return
		self.fillArr(root.left, arr)
		arr.append(root.data)
		self.fillArr(root.right, arr)

	def setBST(self, root, arr, index):
		if root is None:
			return
		self.setBST(root.left, arr, index)
		root.data = arr[index[0]]
		index[0] += 1
		self.setBST(root.right, arr, index)


class Solution:

	def transformTree(self, root):
		stck = []
		current = root
		temp = 0
		while True:
			if current is not None:
				stck.append(current)
				current = current.right
			elif stck:
				current = stck.pop()
				tmp = current.data
				current.data = temp
				temp += tmp
				current = current.left
			else:
				break
		return root


from collections import defaultdict

class Solution:

	def transformTree(self, root):
		self.sum = 0

		def dfs(root):
			if not root:
				return
			dfs(root.right)
			self.sum += root.data
			root.data = self.sum - root.data
			dfs(root.left)
		dfs(root)
		return root


class Solution:

	def transformTree(self, root):
		sum = 0

		def pos(r):
			nonlocal sum
			if r:
				pos(r.right)
				p = r.data
				r.data = sum
				sum += p
				pos(r.left)
		pos(root)


class Solution:

	def transformTree(self, root):

		def my(root):
			if not root:
				return
			my(root.left)
			res.append(root.data)
			my(root.right)

		def my_(root):
			if not root:
				return
			my_(root.left)
			root.data = res[0]
			res.pop(0)
			my_(root.right)
		res = []
		my(root)
		s = sum(res)
		su = 0
		for i in range(len(res)):
			su += res[i]
			res[i] = s - su
		my_(root)
		return root


class Solution:

	def transformTree(self, root):
		sorted = []

		def solve(node):
			if node is None:
				return
			else:
				l = solve(node.left)
				sorted.append(node.data)
				r = solve(node.right)
		solve(root)
		suff = [0] * len(sorted)
		s = 0
		for i in range(len(sorted) - 1, -1, -1):
			s += sorted[i]
			suff[i] = s
		suff.append(0)
		curr = [0]

		def populate(node):
			if node is None:
				return 0
			populate(node.left)
			node.data = suff[curr[0] + 1]
			curr[0] += 1
			populate(node.right)
		populate(root)


class Solution:

	def transformTree(self, root):
		pre_sum = []

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			pre_sum.append(root.data)
			inorder(root.right)
			return
		inorder(root)
		v = 0
		for i in range(len(pre_sum) - 1, -1, -1):
			temp = pre_sum[i]
			pre_sum[i] = v
			v += temp
		i = 0

		def func(root):
			nonlocal i
			if not root:
				return
			func(root.left)
			root.data = pre_sum[i]
			i += 1
			func(root.right)
			return root
		return func(root)


class Solution:

	def transformTree(self, root, extra=0):
		if root is None:
			return 0
		root_right_sum = self.transformTree(root.right, extra=extra)
		old_data = root.data
		root.data = root_right_sum + extra
		root_left_sum = self.transformTree(root.left, extra=old_data + root.data)
		return root_left_sum + root_right_sum + old_data


class Solution:

	def transformTree(self, root):
		s = 0

		def dfs(r):
			nonlocal s
			if not r:
				return
			dfs(r.right)
			temp = r.data
			r.data = s
			s += temp
			dfs(r.left)
		dfs(root)
		return root


class Solution:

	def transformTree(self, root):

		def recur(node, gsum):
			if not node:
				return gsum
			gsum = recur(node.right, gsum)
			temp = node.data
			node.data = gsum
			gsum += temp
			gsum = recur(node.left, gsum)
			return gsum
		recur(root, 0)
		return root


def fun(root, carry):
	if root == None:
		return
	if root.left == None and root.right == None:
		temp = root.data
		root.data = carry[0]
		carry[0] += temp
	else:
		r = fun(root.right, carry)
		temp = root.data
		root.data = carry[0]
		carry[0] += temp
		fun(root.left, carry)

class Solution:

	def transformTree(self, root):
		carry = [0]
		fun(root, carry)
		return root


class Solution:

	def ino(self, r, l):
		if r is None:
			return
		self.ino(r.left, l)
		l.append(r)
		self.ino(r.right, l)

	def transformTree(self, root):
		l = []
		self.ino(root, l)
		s = 0
		n = len(l)
		for i in range(n - 1, -1, -1):
			g = l[i].data
			l[i].data = s
			s += g


class Solution:

	def transformTree(self, root):
		curSum = 0

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


class Solution:
	a = 0

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

	def transformTree(self, root):
		Solution.a = 0
		x = root
		self.f(root)
		return x


class Solution:

	def __init__(self):
		self.sum = 0

	def _transformTree(self, root):
		if not root:
			return
		self._transformTree(root.right)
		tmp = root.data
		root.data = self.sum
		self.sum += tmp
		self._transformTree(root.left)

	def transformTree(self, root):
		self._transformTree(root)
		return root


class Solution:

	def transformTree(self, root):
		global s
		s = 0
		solve(root)
		return root

def solve(root):
	global s
	if not root:
		return
	solve(root.right)
	temp = root.data
	root.data = s
	s += temp
	solve(root.left)


class Solution:

	def transformTree(self, root):
		num = [0]

		def post(root, num):
			if root is None:
				return None
			post(root.right, num)
			x = root.data
			root.data = num[0]
			num[0] += x
			post(root.left, num)
		post(root, num)
		return root


class Solution:

	def transformTree(self, root):

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


class Solution:

	def transformTree(self, root):
		inorder = []
		s = 0

		def solve(node):
			nonlocal s
			if not node:
				return
			solve(node.right)
			s += node.data
			node.data = s - node.data
			solve(node.left)
		solve(root)
		return root


class Solution:

	def transformTree(self, root):
		ar = []
		arr = {}
		temp = root

		def inorder(root):
			if root:
				inorder(root.left)
				ar.append(root.data)
				inorder(root.right)
		inorder(temp)
		ar.sort()
		ar = ar[::-1]
		sm = 0
		for it in ar:
			arr[it] = sm
			sm += it

		def update(root):
			if root:
				update(root.left)
				root.data = arr[root.data]
				update(root.right)
		update(root)
		return root


class Solution:

	def transformTree(self, root):
		prev = 0

		def solve(root):
			nonlocal prev
			if root:
				solve(root.right)
				tmp = root.data
				root.data = prev
				prev = prev + tmp
				solve(root.left)
		solve(root)
		return root


class Solution:

	def transformTree(self, root):
		curr = [0]

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


rsm = 0

def rev_inord(root, rsm):
	if root is None:
		return
	if root.right:
		rsm = rev_inord(root.right, rsm)
	el = root.data
	root.data = rsm
	rsm = rsm + el
	if root.left:
		rsm = rev_inord(root.left, rsm)
	return rsm

class Solution:

	def transformTree(self, root):
		rsm = 0
		rsm = rev_inord(root, rsm)
		return root


class Solution:

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

	def transformTree(self, root):
		t = [0]
		self.rec(root, t)


class Solution:

	def transformTree(self, root):
		s = 0

		def pos(r):
			nonlocal s
			if not r:
				return
			pos(r.right)
			p = r.data
			r.data = s
			s += p
			pos(r.left)
		pos(root)


class Solution:

	def transformTree(self, root):
		self.sum = 0

		def solve(root):
			if root is None:
				return
			solve(root.right)
			num = root.data
			root.data = self.sum
			self.sum += num
			solve(root.left)
		solve(root)


class Solution:

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

	def transformTree(self, root):
		val = [0]
		res = []
		self.postorder(root, res, val)
		return root


class Solution:

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

		def ino(root, pre):
			if not root:
				return
			ino(root.right, pre)
			pre = root.data
			root.data = self.s
			self.s += pre
			ino(root.left, pre)
		ino(root, 0)
		return root
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

def inOrder(root):
	if root == None:
		return
	inOrder(root.left)
	print(root.data, end=' ')
	inOrder(root.right)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		ob = Solution()
		ob.transformTree(root)
		inOrder(root)
		print()


class Solution:

	def inorder(self, root):
		if root is None:
			return []
		return self.inorder(root.left) + [root.data] + self.inorder(root.right)

	def transformTree(self, root):
		if root is None:
			return None
		arr = self.inorder(root)
		st = []
		temp = root
		i = 0
		cumsum = 0
		while st or temp:
			while temp:
				st.append(temp)
				temp = temp.right
			t = st.pop()
			data = t.data
			t.data = cumsum
			cumsum += data
			i += 1
			if t.left:
				temp = t.left
		return root
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

def inOrder(root):
	if root == None:
		return
	inOrder(root.left)
	print(root.data, end=' ')
	inOrder(root.right)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		ob = Solution()
		ob.transformTree(root)
		inOrder(root)
		print()


class Solution:

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

	def transformTreeUtil(self, root, sm):
		if root == None:
			return sm
		l = self.transformTreeUtil(root.left, sm)
		val = root.data
		root.data = total - l - root.data
		r = self.transformTreeUtil(root.right, val + l)
		return r

	def transformTree(self, root):
		global total
		total = self.get_sum(root)
		self.transformTreeUtil(root, 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

def inOrder(root):
	if root == None:
		return
	inOrder(root.left)
	print(root.data, end=' ')
	inOrder(root.right)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		ob = Solution()
		ob.transformTree(root)
		inOrder(root)
		print()