Consider Red lines of slope -1 passing between nodes (in following diagram). The diagonal sum in a binary tree is the sum of all nodes data lying between these lines. Given a Binary Tree of size N, print all diagonal sums.
For the following input tree, output should be 9, 19, 42.
9 is sum of 1, 3 and 5.
19 is sum of 2, 6, 4 and 7.
42 is sum of 9, 10, 11 and 12.
Example 1:
Input:
         4
       /   \
      1     3
           /
          3
Output: 7 4 
Example 2:
Input:
           10
         /    \
        8      2
       / \    /
      3   5  2
Output: 12 15 3 
Your Task:
You don't need to take input. Just complete the function diagonalSum() that takes root node of the tree as parameter and returns an array containing the diagonal sums for every diagonal present in the tree with slope -1.
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(N).
Constraints:
1<=Number of nodes<=10^{5}
Note: The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Difficulty: EASY
Tags: Tree algorithms

Data structures

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3



'''

# Node Class:

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''

#Complete the function below

def diagonalSum(root):

    #:param root: root of the given tree.

    

    #code here

    

    

    

Solutions:
def diagonalSum(root):
	ans = []
	if root == None:
		return ans
	queue = []
	queue.append(root)
	while True:
		if len(queue) == 0:
			break
		s = len(queue)
		curr = 0
		while s > 0:
			temp = queue.pop(0)
			while temp != None:
				curr += temp.data
				if temp.left:
					queue.append(temp.left)
				temp = temp.right
			s -= 1
		ans.append(curr)
	return ans


def diagonalSum(root):
	q = [root]
	res = []
	while q:
		l = len(q)
		t = 0
		for i in range(l):
			p = q.pop(0)
			while p:
				t += p.data
				if p.left:
					q.append(p.left)
				p = p.right
		res.append(t)
	return res


def diagonalSum(root):
	d = dict()

	def helper(root, c, d):
		if root == None:
			return
		if c in d:
			d[c] += root.data
		else:
			d[c] = root.data
		helper(root.left, c + 1, d)
		helper(root.right, c, d)
	helper(root, 0, d)
	l = list(d.keys())
	res = []
	for i in l:
		res.append(d[i])
	return res


def fun(root, level, l):
	if root == None:
		return
	if level >= len(l):
		l.append(root.data)
	else:
		l[level] += root.data
	fun(root.right, level, l)
	fun(root.left, level + 1, l)

def diagonalSum(root):
	l = []
	fun(root, 0, l)
	return l


def diagonalSum(root):
	dictt = dict()
	solve(root, dictt)
	myData = [data[1] for data in sorted(dictt.items(), reverse=True)]
	return myData

def solve(root, dictt, checks=0):
	if root == None:
		return None
	gett = dictt.get(checks)
	dictt[checks] = (0 if gett == None else gett) + root.data
	if root.left != None:
		solve(root.left, dictt, checks - 1)
	if root.right != None:
		solve(root.right, dictt, checks)
	return


def diagonalSum(root):
	queue = [(root, 0)]
	res = {}
	while queue:
		for i in queue:
			(q, cur) = queue.pop(0)
			if q.left:
				queue.append([q.left, cur + 1])
			if q.right:
				queue.append([q.right, cur])
			if cur in res:
				res[cur] += q.data
			else:
				res[cur] = q.data
	return list(res.values())


def diagonalSum(root):
	q = [(root, 0)]
	dic = {}
	while q:
		for i in range(len(q)):
			node1 = q.pop(0)
			node = node1[0]
			cur = node1[1]
			if node.left:
				q.append((node.left, cur + 1))
			if node.right:
				q.append((node.right, cur))
			if cur not in dic:
				dic[cur] = node.data
			else:
				dic[cur] += node.data
	ans = []
	for i in dic:
		ans.append(dic[i])
	return ans


def diagonalSum(root):
	queue = [root]
	ans = []
	while queue:
		n = len(queue)
		sum = 0
		while n > 0:
			temp = queue.pop(0)
			while temp:
				if temp.left:
					queue.append(temp.left)
				sum += temp.data
				temp = temp.right
			n = n - 1
		ans.append(sum)
	return ans


from collections import deque

def diagonalSum(root):
	sums = []
	sum = 0
	dq = deque()
	dq.append(root)
	while len(dq) > 0:
		currsize = len(dq)
		sum = 0
		for i in range(currsize):
			temp = dq.popleft()
			while temp != None:
				sum += temp.data
				if temp.left != None:
					dq.append(temp.left)
				temp = temp.right
		sums.append(sum)
	return sums


def diagonalSum(root):
	ar = []
	d = dict()

	def dfs(root, k):
		if root == None:
			return
		if k not in d.keys():
			d[k] = root.data
		else:
			d[k] += root.data
		dfs(root.left, k + 1)
		dfs(root.right, k)
	dfs(root, 0)
	for i in d.keys():
		ar.append(d[i])
	return ar


def rec(r, dsum, vd):
	if r == None:
		return
	dsum[vd] += r.data
	rec(r.left, dsum, vd + 1)
	rec(r.right, dsum, vd)

def diagonalSum(root):
	dsum = [0] * 100001
	rec(root, dsum, 0)
	i = 0
	res = []
	while dsum[i] != 0:
		res.append(dsum[i])
		i += 1
	return res


def diagonalSum(root):
	sums = {}

	def traverse(root, distance):
		if root == None:
			return
		if distance in sums:
			sums[distance] += root.data
		else:
			sums[distance] = root.data
		traverse(root.left, distance + 1)
		traverse(root.right, distance)
	traverse(root, 0)
	return list(sums.values())


from collections import defaultdict

def diagonalSum(root):
	d = defaultdict(int)

	def dfs(root, level):
		if not root:
			return
		d[level] += root.data
		dfs(root.left, level + 1)
		dfs(root.right, level)
	dfs(root, 0)
	return d.values()


def height(root, h):
	if root is None:
		return h
	return max(max(h, height(root.left, h + 1)), height(root.right, h + 1))

def preorder(root, i, j, mat):
	if root is None:
		return mat
	mat[i][j] += root.data
	mat = preorder(root.left, i + 1, j - 1, mat)
	mat = preorder(root.right, i + 1, j + 1, mat)
	return mat

def diagonalSum(root):
	mat = {}
	h = height(root, 0)
	x = 0
	for i in range(h):
		mat[i] = {}
		for j in range(i + 1):
			mat[i][-j] = 0
			mat[i][j] = 0
			x = min(x, -j)
	preorder(root, 0, 0, mat)
	res = []
	while x <= 0:
		sum = 0
		j = x
		for i in range(0, h):
			if mat[i].get(j) is None:
				continue
			sum += mat[i].get(j, 0)
			j += 1
		if sum:
			res.append(sum)
		x += 1
	res.reverse()
	return res


def util(root, lval, dic):
	if not root:
		return
	dic[lval] = dic.get(lval, 0) + root.data
	if root.left:
		util(root.left, lval + 1, dic)
	if root.right:
		util(root.right, lval, dic)

def diagonalSum(root):
	dic = {}
	lval = 0
	util(root, lval, dic)
	res = []
	for i in sorted(dic.keys()):
		res.append(dic[i])
	return res


def diagonalSum(root):
	obj = Tree()
	return obj.sumGenerator(root)

class Tree:

	def __init__(self):
		self.levels = {}

	def diagonal(self, root, depth=0):
		if root is None:
			return None
		elif depth not in self.levels:
			self.levels[depth] = [root.data]
		else:
			self.levels[depth].append(root.data)
		self.diagonal(root.left, depth + 1)
		self.diagonal(root.right, depth)

	def sumGenerator(self, root):
		self.diagonal(root)
		res = []
		for (k, v) in self.levels.items():
			res.append(sum(v))
		return res


def diagonalSum(root):
	results = {}

	def diagTraverse(node, m):
		nonlocal results
		if node.left:
			diagTraverse(node.left, m + 1)
		if node.right:
			diagTraverse(node.right, m)
		if m in results:
			results[m] += node.data
		else:
			results[m] = node.data
	diagTraverse(root, 0)
	return list(results.values())


def diagonalSum(root):

	def helper(root, d, count):
		if root == None:
			return
		if count in d:
			d[count].append(root.data)
		else:
			d[count] = [root.data]
		helper(root.left, d, count + 1)
		helper(root.right, d, count)
	d = {}
	c = []
	helper(root, d, 0)
	for (k, v) in sorted(d.items()):
		c.append(sum(v))
	return c


def diagonalSum(root):
	ds = {}

	def helper(root, vd, ds):
		if not root:
			return
		if vd not in ds:
			ds[vd] = 0
		ds[vd] += root.data
		helper(root.left, vd + 1, ds)
		helper(root.right, vd, ds)
	helper(root, 0, ds)
	ans = []
	for i in ds:
		ans.append(ds[i])
	return ans


def diagonalSum(root):
	A = []
	x(root, A, 0, 0)
	L = 0
	for i in range(len(A)):
		if A[i][1] > L:
			L = A[i][1]
	D = {}
	for i in range(len(A)):
		if A[i][1] + A[i][2] not in D.keys():
			D[A[i][1] + A[i][2]] = A[i][0]
		else:
			D[A[i][1] + A[i][2]] += A[i][0]
	E = []
	for i in sorted(D.keys()):
		E.append(D[i])
	return E

def x(root, A, level, hd):
	if root:
		x(root.left, A, level + 1, hd + 1)
		A.append([root.data, level, hd])
		x(root.right, A, level + 1, hd - 1)


def diagonalSum(root):

	def solve(root, dd, dic):
		if root == None:
			return
		if dd not in dic:
			dic[dd] = [root.data]
		else:
			dic[dd].append(root.data)
		solve(root.left, dd - 1, dic)
		solve(root.right, dd, dic)
		return dic
	dicc = solve(root, 0, {})
	lis = []
	arr = sorted(dicc.keys(), reverse=True)
	for i in arr:
		lis.append(sum(dicc[i]))
	return lis


from collections import OrderedDict

def diagonalSum(root):
	d = OrderedDict()
	dfs(root, d, 0)
	res = []
	for i in d:
		res.append(d[i])
	return res

def dfs(root, d, k):
	if root:
		if k not in d:
			d[k] = 0
		d[k] += root.data
		dfs(root.left, d, k - 1)
		dfs(root.right, d, k)


def diagonalSum(root):
	if root == None:
		return 0
	arr = [root]
	ans = []
	while arr:
		total = 0
		length = len(arr)
		for i in range(length):
			ele = arr.pop(0)
			while ele:
				total += ele.data
				if ele.left:
					arr.append(ele.left)
				ele = ele.right
		ans.append(total)
	return ans


def diagonalSum(root):
	sums = []

	def rightfirstSum(root, pos):
		if pos in range(len(sums)):
			sums[pos] += root.data
		else:
			sums.append(root.data)
		if root.right is not None:
			rightfirstSum(root.right, pos)
		if root.left is not None:
			rightfirstSum(root.left, pos + 1)
		return
	rightfirstSum(root, 0)
	return sums


def diagonalSum(root):
	result = dict()
	diagonalSumUtil(root, 0, result)
	rlist = []
	for key in result:
		rlist.append(result[key])
	return rlist

def diagonalSumUtil(root, dist, result):
	if root is None:
		return
	if dist not in result:
		result[dist] = 0
	result[dist] += root.data
	diagonalSumUtil(root.left, dist + 1, result)
	diagonalSumUtil(root.right, dist, result)


def diagonalSum(root):
	d = {}

	def dfs(root, diagonal, d):
		if root is None:
			return
		d[diagonal] = d.get(diagonal, 0) + root.data
		dfs(root.left, diagonal + 1, d)
		dfs(root.right, diagonal, d)
	dfs(root, 0, d)
	return [v for v in d.values()]


from collections import Counter

def diagonalSum(root):
	c = Counter()
	myFunc(root, c, 0, 0)
	return [c[item] for item in sorted(c)][::-1]

def myFunc(root, c, line, level):
	if not root:
		return
	c[line - level] += root.data
	myFunc(root.left, c, line - 1, level + 1)
	myFunc(root.right, c, line + 1, level + 1)
	return


def diagonalSum(root):
	d = {}
	level = 0
	l = []
	if not root:
		return []
	helper(root, level, d)
	d1 = sorted(d.keys(), reverse=True)
	for i in d1:
		l.append(sum(d[i]))
	return l

def helper(root, level, d):
	if not root:
		return
	if level not in d:
		d[level] = [root.data]
	else:
		d[level].append(root.data)
	helper(root.left, level - 1, d)
	helper(root.right, level, d)


def diagonalSum(root):
	li = []
	st = []
	count = 0
	last = 0
	sum = 0
	while root != None:
		if root.left:
			st.append(root.left)
			count += 1
		sum += root.data
		root = root.right
		if root == None:
			if len(st) != 0:
				root = st.pop(0)
			if last == 0:
				li.append(sum)
				sum = 0
				last = count
				count = 0
			last -= 1
	return li


def diagonalSumUtil(root, vd, diagonalSum):
	if not root:
		return
	if vd not in diagonalSum:
		diagonalSum[vd] = 0
	diagonalSum[vd] += root.data
	diagonalSumUtil(root.left, vd + 1, diagonalSum)
	diagonalSumUtil(root.right, vd, diagonalSum)

def diagonalSum1(root):
	diagonalSum = dict()
	diagonalSumUtil(root, 0, diagonalSum)
	ans = []
	for it in diagonalSum:
		ans.append(diagonalSum[it])
	return ans

def diagonalSum(root):
	return diagonalSum1(root)


def diagonalSum(root):
	q = [root]
	result = []
	while len(q):
		n = len(q)
		total = 0
		while n:
			n -= 1
			curr = q[0]
			del q[0]
			if curr.left != None:
				q.append(curr.left)
			if curr.right != None:
				while curr != None:
					total += curr.data
					curr = curr.right
					if curr != None and curr.left != None:
						q.append(curr.left)
			else:
				total += curr.data
		result.append(total)
	return result


def diagonalSum(root):
	if root == None:
		return 0
	hd = 0
	q = [[root, hd]]
	dict1 = dict()
	while q != []:
		node = q.pop(0)
		if node[-1] not in dict1:
			dict1[node[-1]] = node[0].data
		else:
			dict1[node[-1]] += node[0].data
		hd = node[-1]
		if node[0].left:
			q.append([node[0].left, hd + 1])
		if node[0].right:
			q.append([node[0].right, hd])
	list1 = sorted(dict1.items(), key=lambda x: x[0])
	return list(map(lambda x: x[1], list1))


def diagonalSum(root):
	q = []
	q.append(root)
	res = []
	while q:
		curr_size = len(q)
		curr_sum = 0
		while curr_size > 0:
			node = q.pop(0)
			curr_size -= 1
			while node:
				curr_sum += node.data
				if node.left:
					q.append(node.left)
				node = node.right
		res.append(curr_sum)
	return res


def diagonalSum(root):
	res = {}
	final = []
	diagonalSumHelper(root, res, 0)
	for key in res:
		final.append(res[key])
	return final

def diagonalSumHelper(root, res, i):
	if root == None:
		return
	if i in res:
		temp = res[i]
		temp = temp + root.data
		res[i] = temp
	else:
		res[i] = root.data
	diagonalSumHelper(root.left, res, i + 1)
	diagonalSumHelper(root.right, res, i)


def diagonalSum(root):
	dic = {}
	cnt = 0
	q = [[root, cnt]]
	while q:
		if q[0][1] not in dic:
			dic.update({q[0][1]: q[0][0].data})
		else:
			dic[q[0][1]] += q[0][0].data
		if q[0][0].right:
			a = [q[0][0].right, q[0][1]]
			q.append(a)
		if q[0][0].left:
			a = [q[0][0].left, q[0][1] + 1]
			q.append(a)
		q.pop(0)
	ans = []
	for i in dic:
		ans.append(dic[i])
	return ans


def diagonalSum(root):

	def helper(root, mp, k):
		if root != None:
			if k in mp:
				mp[k].append(root.data)
			else:
				mp[k] = [root.data]
			helper(root.left, mp, k + 1)
			helper(root.right, mp, k)
	mp = {}
	k = 0
	helper(root, mp, k)
	res = []
	for k in mp:
		res.append(sum(mp[k]))
	return res


def diagonalSum(root):
	q = [[root, 0]]
	m = {}
	c = 0
	while c != len(q):
		t = q[c][0]
		g = q[c][1]
		while t is not None:
			if g not in m:
				m[g] = t.data
			else:
				m[g] += t.data
			if t.left:
				q.append([t.left, g + 1])
			t = t.right
		c += 1
	l = []
	for i in sorted(m):
		l.append(m[i])
	return l


def diagonalSum(root):
	q = [root]
	res = []
	while q:
		n = len(q)
		total = 0
		for _ in range(n):
			cur = q.pop(0)
			while cur:
				if cur.left:
					q.append(cur.left)
				total += cur.data
				cur = cur.right
		res.append(total)
	return res


def diagonalSum(root):
	res = []
	queue = []
	queue.append(root)
	while queue:
		count = len(queue)
		total = 0
		for i in range(count):
			curr = queue.pop(0)
			while curr:
				if curr.left:
					queue.append(curr.left)
				total += curr.data
				curr = curr.right
		res.append(total)
	return res


from collections import defaultdict

def diagonalSum(root):
	sums = defaultdict(int)
	max_diag = [0]

	def rec(root, diagonal):
		if not root:
			return
		sums[diagonal] += root.data
		max_diag[0] = max(max_diag[0], diagonal)
		rec(root.left, diagonal + 1)
		rec(root.right, diagonal)
	rec(root, 0)
	return [sums[i] for i in range(max_diag[0] + 1)]


def diagonalSum(root):

	def f(root, v):
		if root == None:
			return
		if v not in d.keys():
			d[v] = 0
		d[v] += root.data
		f(root.left, v + 1)
		f(root.right, v)
	d = {}
	f(root, 0)
	r = []
	for i in sorted(d.keys()):
		r.append(d[i])
	return r


from collections import defaultdict

def solve(root, m, d):
	if root == None:
		return
	m[d] += root.data
	if root.left:
		solve(root.left, m, d + 1)
	if root.right:
		solve(root.right, m, d)

def diagonalSum(root):
	m = defaultdict(int)
	l = [root]
	d = 0
	solve(root, m, d)
	return m.values()


def dump(root, vd, d):
	if root == None:
		return
	if vd not in d.keys():
		d[vd] = 0
	d[vd] += root.data
	dump(root.left, vd + 1, d)
	dump(root.right, vd, d)

def diagonalSum(root):
	if root == None:
		return None
	d = dict()
	dump(root, 0, d)
	ans = [v for v in d.values()]
	return ans


def diagonalSum(root):

	def solve(root, diag, diagDict):
		if root is None:
			return
		if diag in diagDict:
			diagDict[diag].append(root.data)
		else:
			diagDict[diag] = [root.data]
		solve(root.left, diag + 1, diagDict)
		solve(root.right, diag, diagDict)
	diag = 0
	diagDict = {}
	solve(root, diag, diagDict)
	mini = min(diagDict)
	maxi = max(diagDict)
	res = []
	for key in range(mini, maxi + 1):
		sum = 0
		for ele in diagDict[key]:
			sum += ele
		res.append(sum)
	return res


def inorder(root, d, lvl):
	if root is None:
		return
	if root:
		inorder(root.right, d, lvl)
		if lvl in d:
			d[lvl] += root.data
		else:
			d[lvl] = root.data
		inorder(root.left, d, lvl + 1)
	return

def diagonalSum(root):
	d = {}
	lvl = 0
	inorder(root, d, lvl)
	return list(d.values())


from collections import *

def diagonalSum(root):
	visited = set()
	ans = []
	queue = deque()
	queue.append(root)
	while queue:
		s = 0
		for _ in range(len(queue)):
			node = queue.popleft()
			s += node.data
			visited.add(node)
			while node.right:
				s += node.right.data
				if node.left:
					visited.add(node.left)
					queue.append(node.left)
				node = node.right
			if node.left:
				queue.append(node.left)
		ans.append(s)
	return ans


def diagonalSum(root):
	ans = {}
	i = 0
	sumtree(root, ans, i)
	return ans.values()

def sumtree(root, ans, i):
	if root == None:
		return
	if i not in ans:
		ans[i] = 0
	ans[i] += root.data
	sumtree(root.left, ans, i + 1)
	sumtree(root.right, ans, i)


def diagonalSum(root):
	result = []
	res = []
	q = []
	q.append(root)
	while len(q):
		count = len(q)
		ans = []
		while count:
			temp = q.pop(0)
			while temp:
				ans.append(temp.data)
				if temp.left:
					q.append(temp.left)
				temp = temp.right
			count -= 1
		res.append(ans)
	for i in res:
		result.append(sum(i))
	return result


def diagonalSumUtils(root, level, mp):
	if root is None:
		return
	if level in mp:
		mp[level] += root.data
	else:
		mp[level] = root.data
	diagonalSumUtils(root.left, level + 1, mp)
	diagonalSumUtils(root.right, level, mp)

def diagonalSum2(root):
	if root is None:
		return []
	mp = {}
	diagonalSumUtils(root, 0, mp)
	return mp.values()

def diagonalSum(root):
	if root is None:
		return []
	mp = {root: 0}
	res = {}
	q = []
	q.append(root)
	while len(q):
		temp = q.pop(0)
		level = mp[temp]
		if level in res:
			res[level] += temp.data
		else:
			res[level] = temp.data
		if temp.left:
			mp[temp.left] = level + 1
			q.append(temp.left)
		right = temp.right
		if right:
			mp[right] = level
			q.append(right)
	return res.values()


def diagonalSumUtils(root, level, mp):
	if root is None:
		return
	if level in mp:
		mp[level] += root.data
	else:
		mp[level] = root.data
	diagonalSumUtils(root.left, level + 1, mp)
	diagonalSumUtils(root.right, level, mp)

def diagonalSum(root):
	if root is None:
		return []
	mp = {}
	diagonalSumUtils(root, 0, mp)
	return mp.values()


def diagonalSum(root):
	m = {}

	def solve(r, i):
		if r != None:
			if i not in m:
				m[i] = r.data
			else:
				m[i] += r.data
			solve(r.left, i + 1)
			solve(r.right, i)
	ans = []
	solve(root, 1)
	for key in m.keys():
		ans.append(m[key])
	return ans


def diagonalSum(root):
	q = deque()
	q.append(root)
	qv = deque()
	qv.append(0)
	dic = {}
	while q:
		l = len(q)
		for i in range(l):
			x = q.popleft()
			v = qv.popleft()
			if v in dic:
				dic[v] += x.data
			else:
				dic[v] = x.data
			if x.left:
				q.append(x.left)
				qv.append(v - 1)
			if x.right:
				q.append(x.right)
				qv.append(v)
	arr = []
	lst = list(dic.keys())
	lst.sort(reverse=True)
	for key in lst:
		arr.append(dic[key])
	return arr


def diagonalSum(root):
	digsum = dict()
	vd = 0
	helperfn(root, vd, digsum)
	ans = []
	for i in digsum:
		ans.append(digsum[i])
	return ans

def helperfn(root, vd, digsum):
	if root is None:
		return
	if vd not in digsum:
		digsum[vd] = 0
	digsum[vd] += root.data
	helperfn(root.left, vd + 1, digsum)
	helperfn(root.right, vd, digsum)


from collections import defaultdict

def logic(root, ans, hori):
	if root is None:
		return
	ans[hori].append(root.data)
	logic(root.left, ans, hori + 1)
	logic(root.right, ans, hori)

def diagonalSum(root):
	ans = defaultdict(list)
	result = []
	logic(root, ans, 0)
	for key in ans:
		result.append(sum(ans[key]))
	return result


def dsum(root, vd, d):
	if not root:
		return
	if vd not in d:
		d[vd] = 0
	d[vd] += root.data
	dsum(root.left, vd + 1, d)
	dsum(root.right, vd, d)

def diagonalSum(root):
	if root is None:
		return
	d = dict()
	dsum(root, 0, d)
	res = []
	for ele in d:
		res.append(d[ele])
	return res


from collections import deque

def diagonalSum(root):
	ans = deque()
	q = deque()
	c = 0
	prev = 0
	s = 0
	while root != None:
		if root.left is not None:
			q.append(root.left)
			c += 1
		s += root.data
		root = root.right
		if root is None:
			if len(q) != 0:
				root = q.popleft()
			if prev == 0:
				ans.append(s)
				prev = c
				c = 0
				s = 0
			prev -= 1
	return ans


def diagonalSum(root):
	hashmap = {}

	def dfs(root, vd):
		if root is None:
			return
		hashmap[vd] = root.data + hashmap.get(vd, 0)
		dfs(root.left, vd + 1)
		dfs(root.right, vd)
	dfs(root, 0)
	return hashmap.values()
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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		res = diagonalSum(root)
		for i in res:
			print(i, end=' ')
		print()


def diagonalSum(root):

	def getSums(node, lis, depth):
		if node is None:
			return
		try:
			lis[depth] += node.data
		except:
			lis.append(node.data)
		getSums(node.right, lis, depth)
		getSums(node.left, lis, depth + 1)
	lis = []
	getSums(root, lis, 0)
	return lis
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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		res = diagonalSum(root)
		for i in res:
			print(i, end=' ')
		print()


def diagonalSum(root):
	ans = []
	queue = [root]
	while queue:
		n = len(queue)
		sum = 0
		for _ in range(n):
			cur = queue.pop(0)
			while cur:
				sum += cur.data
				if cur.left:
					queue.append(cur.left)
				cur = cur.right
		ans.append(sum)
	return ans
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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		res = diagonalSum(root)
		for i in res:
			print(i, end=' ')
		print()


from collections import defaultdict

def diagonalSum(root):
	hashh = defaultdict(list)

	def solve(root, cur_val, c):
		if root:
			c[0] += 1
			nonlocal hashh
			hashh[cur_val].append(root)
			solve(root.left, cur_val + 1, c)
			solve(root.right, cur_val, c)
	c = [0]
	solve(root, 0, c)
	result = [0] * len(hashh)
	for (key, val) in hashh.items():
		summ = 0
		for i in val:
			summ += i.data
		result[key] = summ
	return result
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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		res = diagonalSum(root)
		for i in res:
			print(i, end=' ')
		print()


def find_sum_of_each_levels(node, ht, level):
	if node == None:
		return
	if level in ht.keys():
		ht[level] = ht[level] + node.data
	else:
		ht[level] = node.data
	find_sum_of_each_levels(node.left, ht, level + 1)
	find_sum_of_each_levels(node.right, ht, level)

def diagonalSum(root):
	ht = dict()
	find_sum_of_each_levels(root, ht, 0)
	final_ans = []
	verticalLevels = list(ht.keys())
	verticalLevels.sort()
	for vLLevel in verticalLevels:
		final_ans.append(ht[vLLevel])
	return final_ans
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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		res = diagonalSum(root)
		for i in res:
			print(i, end=' ')
		print()


def diagonalSum(root):
	length = height(root)
	ans = [0] * length
	diag(root, 0, 0, ans)
	return ans

def diag(root, l, r, ans):
	if root != None:
		ans[l] += root.data
		diag(root.left, l + 1, r, ans)
		diag(root.right, l, r, ans)

def height(root):
	if not root:
		return 0
	lh = height(root.left) + 1
	rh = height(root.right) + 0
	return max(lh, rh)
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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		res = diagonalSum(root)
		for i in res:
			print(i, end=' ')
		print()


def diagonalSum(root):
	s = []
	d = dict()
	d[0] = []
	d[0].append(root)
	s.append([root, 0])
	res = []
	while s:
		[itr, sp] = s.pop()
		if itr.left:
			try:
				d[sp + 1].append(itr.left)
			except:
				d[sp + 1] = []
				d[sp + 1].append(itr.left)
			s.append([itr.left, sp + 1])
		if itr.right:
			s.append([itr.right, sp])
			d[sp].append(itr.right)
	for i in sorted(d.keys()):
		res.append(sum([j.data for j in d[i]]))
	return res
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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		res = diagonalSum(root)
		for i in res:
			print(i, end=' ')
		print()


def diagonalSum(root):
	q = [[root, 1]]
	hm = {}
	arr = []
	while q:
		t = q.pop(0)
		a = t[0]
		b = t[1]
		while a:
			if a.left:
				q.append([a.left, b + 1])
			if hm.get(b):
				hm[b] += a.data
			else:
				hm[b] = a.data
				arr.append(b)
			a = a.right
	arr.sort()
	for i in range(len(arr)):
		arr[i] = hm[arr[i]]
	return arr
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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		res = diagonalSum(root)
		for i in res:
			print(i, end=' ')
		print()


def summerize(root, x, level=0):
	if root is None:
		return 0
	if level not in x:
		x[level] = 0
	x[level] += root.data
	summerize(root.right, x, level)
	summerize(root.left, x, level + 1)

def diagonalSum(root):
	x = dict()
	summerize(root, x)
	return x.values()


from collections import deque

def diagonalSum(root):
	q = deque()
	q.append(root)
	level = 0
	mapp = {}
	mapp[root] = 0
	hd = {}
	hd[mapp[root]] = root.data
	while q:
		cur_size = len(q)
		while cur_size > 0:
			node = q.popleft()
			cur_size -= 1
			if node.left:
				mapp[node.left] = mapp[node] - 1
				if mapp[node.left] not in hd:
					hd[mapp[node.left]] = 0
				hd[mapp[node.left]] += node.left.data
				q.append(node.left)
			if node.right:
				mapp[node.right] = mapp[node]
				if mapp[node.right] not in hd:
					hd[mapp[node.right]] = 0
				hd[mapp[node.right]] += node.right.data
				q.append(node.right)
	ans = [v for (k, v) in sorted(hd.items(), reverse=True)]
	return ans


def diagonalSum(root):
	if root.left == None and root.right == None:
		return root.data
	mapp = {}
	diagonalSumUtil(root, mapp, 0)
	ans = [v for (k, v) in sorted(mapp.items(), reverse=True)]
	return ans

def diagonalSumUtil(root, mapp, level):
	if not root:
		return 0
	if level not in mapp:
		mapp[level] = 0
	mapp[level] += root.data
	diagonalSumUtil(root.left, mapp, level - 1)
	diagonalSumUtil(root.right, mapp, level)


def diagonalSum(root):

	def ds(root, vd, vds):
		if not root:
			return
		if vd not in vds:
			vds[vd] = 0
		vds[vd] += root.data
		ds(root.left, vd + 1, vds)
		ds(root.right, vd, vds)
	vds = {}
	ds(root, 0, vds)
	l = []
	for i in vds.keys():
		l.append(vds[i])
	return l


def diagonalSum(root):
	ans = []

	def dfs(root, digsize):
		if root == None:
			return
		if digsize == len(ans):
			ans.append(0)
		ans[digsize] += root.data
		dfs(root.left, digsize + 1)
		dfs(root.right, digsize)
	dfs(root, 0)
	return ans


def diagonalSum(root):
	deq = deque([root])
	ans = []
	while len(deq) > 0:
		size = len(deq)
		s = 0
		for i in range(size):
			node = deq.popleft()
			while node != None:
				s += node.data
				if node.left != None:
					deq.append(node.left)
				node = node.right
		ans.append(s)
	return ans


mp = {}

def helper(root, k):
	if not root:
		return
	mp[k] = mp[k] + root.data if k in mp else root.data
	helper(root.left, k + 1)
	helper(root.right, k)

def diagonalSum(root):
	if not root:
		return []
	mp.clear()
	res = []
	helper(root, 0)
	for key in sorted(mp):
		res.append(mp[key])
	return res


def solve(root, level, dict):
	if not root:
		return
	if level not in dict.keys():
		dict[level] = []
	dict[level].append(root.data)
	solve(root.right, level, dict)
	solve(root.left, level + 1, dict)

def diagonaldict(root):
	level = 0
	dict = {}
	solve(root, level, dict)
	ans = []
	for x in sorted(dict.items()):
		ans.append(sum(x[1]))
	return ans


def diagonalSumUtil(root, diagonal, d):
	if root is None:
		return
	if diagonal in d:
		prev = d[diagonal]
		prev += root.data
		d.update({diagonal: prev})
	else:
		d.update({diagonal: root.data})
	diagonalSumUtil(root.left, diagonal + 1, d)
	diagonalSumUtil(root.right, diagonal, d)

def diagonalSum(root):
	d = dict()
	diagonalSumUtil(root, 1, d)
	res = []
	for key in d.keys():
		res.append(d[key])
	return res


def diagonalSum(root):
	q = []
	q.append(root)
	l = []
	while len(q) > 0:
		s = 0
		for i in range(len(q)):
			c = q.pop(0)
			d = c
			while c:
				s = s + c.data
				if c.left:
					q.append(c.left)
				c = c.right
		l.append(s)
	return l


from collections import deque

def diagonalSum(root):
	q = deque()
	q.append(root)
	q.append(-1)
	sm = []
	x = 0
	while q:
		curr = q.popleft()
		if curr == -1:
			sm.append(x)
			x = 0
			if q:
				q.append(-1)
				continue
			else:
				break
		while curr:
			x += curr.data
			if curr.left:
				q.append(curr.left)
			curr = curr.right
	return sm


def diagonalSum(root):
	q = []
	q.append(root)
	q.append(None)
	s = []
	arr = []
	while len(q):
		p = q.pop(0)
		if p == None:
			q.append(None)
			p = q.pop(0)
			s.append(sum(arr))
			arr = []
			if p == None:
				break
		while p:
			arr.append(p.data)
			if p.left:
				q.append(p.left)
			p = p.right
	return s


def diagonalSum(root):
	queue = [root]
	res = []
	size = 1
	while len(queue) > 0:
		sum = 0
		while size > 0:
			node = queue.pop(0)
			while node:
				if node.left:
					queue.append(node.left)
				sum += node.data
				node = node.right
			size -= 1
		res.append(sum)
		size = len(queue)
	return res


def diagonalSum(root):
	result = []
	arr = []
	node = root
	r = sum_of_right(node, arr)
	result.append(r)
	while arr:
		s = 0
		arr1 = arr
		arr = []
		for each in arr1:
			s = s + sum_of_right(each, arr)
		result.append(s)
	return result[:-1]

def sum_of_right(root, arr):
	if not root:
		return 0
	arr.append(root.left)
	return root.data + sum_of_right(root.right, arr)


def util(node, val, D):
	if node == None:
		return None
	if val not in D:
		D[val] = [node.data]
	else:
		D[val].append(node.data)
	util(node.left, val + 1, D)
	util(node.right, val, D)
	return D

def diagonalSum(node):
	D = {}
	val = 0
	D = util(node, val, D)
	res = []
	D = dict(sorted(D.items()))
	for i in D:
		res.append(sum(D[i]))
	return res