Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines starting from left-most vertical line to right-most vertical line.
Example 1:
Input:
       1
    /   \
  2      3
 / \    / \
4   5  6   7
Output: 4 2 12 3 7
Explanation:
The tree has 5 vertical lines
Vertical-Line-1 has only one node
4 => vertical sum is 4
Vertical-Line-2: has only one node
2=> vertical sum is 2
Vertical-Line-3: has three nodes:
1,5,6 => vertical sum is 1+5+6 = 12
Vertical-Line-4: has only one node 3
=> vertical sum is 3
Vertical-Line-5: has only one node 7
=> vertical sum is 7
Your Task:
You don't need to take input. Just complete the function verticalSum() that takes root node of the tree as parameter and returns an array containing the vertical sum of tree from left to right.
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(N).
Constraints:
1<=Number of nodes<=1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

# Node Class:

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''

class Solution:

    #Complete the function below

    def verticalSum(self, root):

        #:param root: root of the given tree.

        

        #code here

Solutions:
def slove(root, hd, d):
	if root is None:
		return
	slove(root.left, hd - 1, d)
	if hd in d:
		d[hd] += root.data
	else:
		d[hd] = root.data
	slove(root.right, hd + 1, d)

class Solution:

	def verticalSum(self, root):
		d = {}
		slove(root, 0, d)
		ans = []
		d = sorted(d.items(), key=lambda x: x[0])
		for i in d:
			ans.append(i[1])
		return ans


class Solution:

	def verticalSum(self, root):

		def t(rt, lev, res):
			if rt is None:
				return None
			t(rt.left, lev + 1, res)
			if res.get(lev, ''):
				res[lev].append(rt.data)
			else:
				res[lev] = [rt.data]
			t(rt.right, lev - 1, res)
		r = {}
		t(root, 0, r)
		r1 = []
		v = list(r.keys())
		v.sort(reverse=True)
		for i in v:
			r1.append(sum(r.get(i)))
		return r1


from collections import defaultdict

class Solution:

	def verticalSum(self, root):
		if not root:
			return 0
		queue = [(root, 0)]
		(l, r, hd) = (0, 0, 0)
		m = defaultdict(int)
		m[0] = root.data
		while queue:
			(node, hd) = queue.pop(0)
			(l, r) = (hd, hd)
			if node.left:
				l -= 1
				queue.append((node.left, l))
				if m.get(l) is None:
					m[l] = 0
				m[l] += node.left.data
			if node.right:
				r += 1
				queue.append((node.right, r))
				if m[r] is None:
					m[r] = 0
				m[r] += node.right.data
		m = sorted(m.items())
		ans = [j for (i, j) in m]
		return ans


class Solution:

	def verticalSum(self, root):

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


class Solution:

	def fun(self, root, c, d):
		if root == None:
			return
		if c not in d.keys():
			d[c] = []
		d[c].append(root.data)
		self.fun(root.left, c - 1, d)
		self.fun(root.right, c + 1, d)

	def verticalSum(self, root):
		d = {}
		self.fun(root, 0, d)
		l = []
		for i in d.keys():
			l.append(i)
		t = []
		l.sort()
		for i in l:
			t.append(sum(d[i]))
		return t


class Solution:

	def solve(self, root, dic, cur):
		if root == None:
			return
		if cur not in dic:
			dic[cur] = root.data
		else:
			dic[cur] += root.data
		self.solve(root.left, dic, cur - 1)
		self.solve(root.right, dic, cur + 1)

	def verticalSum(self, root):
		dic = {}
		self.solve(root, dic, 0)
		ans = []
		lis = sorted(dic.keys())
		for i in lis:
			ans.append(dic[i])
		return ans


from collections import deque

class Solution:

	def verticalSum(self, root):
		q = deque([(root, 0)])
		top = 0
		d = {}
		minn = 0
		maxx = 0
		while top >= 0:
			temp = q.popleft()
			top -= 1
			minn = min(minn, temp[1])
			maxx = max(maxx, temp[1])
			if d.get(temp[1]) == None:
				d[temp[1]] = temp[0].data
			else:
				d[temp[1]] += temp[0].data
			if temp[0].left != None:
				q.append([temp[0].left, temp[1] - 1])
				top += 1
			if temp[0].right != None:
				q.append([temp[0].right, temp[1] + 1])
				top += 1
		answer = []
		for i in range(minn, maxx + 1):
			answer.append(d[i])
		return answer


class Solution:

	def verticalSum(self, root):
		import collections
		dic = {}

		def helper(root, line):
			if root is None:
				return
			dic[line] = dic.get(line, 0) + root.data
			helper(root.left, line - 1)
			helper(root.right, line + 1)
		helper(root, 0)
		ans = []
		for key in sorted(dic.keys()):
			ans.append(dic[key])
		return ans


class Solution:

	def verticalSum(self, root):
		import collections
		dic = {}
		queue = collections.deque()
		queue.append([root, 0])
		while queue:
			for _ in range(len(queue)):
				(node, line) = queue.popleft()
				dic[line] = dic.get(line, 0) + node.data
				if node.left:
					queue.append([node.left, line - 1])
				if node.right:
					queue.append([node.right, line + 1])
		ans = []
		for key in sorted(dic.keys()):
			ans.append(dic[key])
		return ans


class Solution:

	def verticalSum(self, root):

		def ver(root, h, mp):
			if root is None:
				return
			if h not in mp:
				mp[h] = root.data
			else:
				mp[h] += root.data
			ver(root.left, h + 1, mp)
			ver(root.right, h - 1, mp)
		mp = {}
		ver(root, 0, mp)
		dmy = []
		for i in mp:
			dmy.append([i, mp[i]])
		dmy.sort()
		ans = []
		for j in range(len(dmy) - 1, -1, -1):
			ans.append(dmy[j][1])
		return ans


class Solution:

	def verticalSum(self, root):
		d = {}
		q = deque()
		q.append((root, 0))
		while q:
			(node, dist) = q.popleft()
			d.setdefault(dist, []).append(node.data)
			if node.left:
				q.append((node.left, dist - 1))
			if node.right:
				q.append((node.right, dist + 1))
		m = []
		for key in sorted(d.keys()):
			m.append(d[key])
		t = []
		for i in m:
			t.append(sum(i))
		return t


import collections

class Solution:

	def verticalSum(self, root):
		mp = {}
		if not root:
			return 0
		q = collections.deque()
		q.append([root, 0])
		while q:
			qLen = len(q)
			for i in range(qLen):
				cur = q.popleft()
				if cur[1] in mp:
					mp[cur[1]] += cur[0].data
				else:
					mp[cur[1]] = cur[0].data
				if cur[0].left:
					q.append([cur[0].left, cur[1] - 1])
				if cur[0].right:
					q.append([cur[0].right, cur[1] + 1])
		(mn, mx) = (min(list(mp.keys())), max(list(mp.keys())))
		res = []
		for i in range(mn, mx + 1):
			res.append(mp[i])
		return res


class Solution:

	def util(self, root, mapper, lvl):
		if not root:
			return
		mapper[lvl].append(root.data)
		self.util(root.left, mapper, lvl - 1)
		self.util(root.right, mapper, lvl + 1)

	def verticalSum(self, root):
		from collections import defaultdict
		ret = defaultdict(list)
		self.util(root, ret, 0)
		res = []
		sm = 0
		for i in sorted(ret):
			sm = 0
			for j in ret[i]:
				sm += j
			res.append(sm)
		return res


from collections import defaultdict

class Solution:

	def verticalSum(self, root):
		map = defaultdict(lambda : 0)

		def helper(root, column):
			if not root:
				return
			helper(root.left, column - 1)
			helper(root.right, column + 1)
			map[column] += root.data
		helper(root, 0)
		res = []
		for k in sorted(map.keys()):
			res.append(map[k])
		return res


class Solution:

	def verticalSum(self, root):
		if root is None:
			return []
		q = []
		mp = {}
		q.append([root, 0])
		while len(q) > 0:
			t = []
			while len(q) != 0:
				x = q.pop(0)
				if x[0].left is not None:
					t.append([x[0].left, x[1] - 1])
				if x[0].right is not None:
					t.append([x[0].right, x[1] + 1])
				if x[1] in mp:
					mp[x[1]] = mp[x[1]] + x[0].data
				else:
					mp[x[1]] = x[0].data
			q = t
		ans = []
		for key in sorted(mp.keys()):
			ans.append(mp[key])
		return ans


class Solution:

	def verticalSum(self, root):
		if not root:
			return []
		opt = []
		q = [[root, 0]]
		res = {}
		while q:
			le = len(q)
			for i in range(le):
				s = q.pop(0)
				(curr, ind) = (s[0], s[1])
				if curr.left:
					q.append([curr.left, ind - 1])
				if curr.right:
					q.append([curr.right, ind + 1])
				if ind not in res:
					res[ind] = [curr.data]
				else:
					res[ind] += [curr.data]
		op = sorted(res.items())
		for (i, j) in op:
			opt.append(sum(j))
		return opt


class Solution:
	from collections import OrderedDict

	def verticalSum(self, root):
		m = {}
		a = []
		hd = 0
		self.verticalT(root, m, hd)
		myKeys = list(m.keys())
		myKeys.sort()
		for i in myKeys:
			a.append(m[i])
		return a

	def verticalT(self, root, m, hd):
		if root is None:
			return
		self.verticalT(root.left, m, hd - 1)
		if hd not in m:
			m[hd] = root.data
		else:
			m[hd] += root.data
		self.verticalT(root.right, m, hd + 1)


class Solution:

	def verticalSum(self, root):

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


class Solution:

	def verticalSum(self, root):
		lis = []
		dic = {}
		q = []
		q.append(root)
		l = [0]
		while q:
			temp = q.pop(0)
			level = l.pop(0)
			if level not in dic:
				dic[level] = temp.data
			else:
				dic[level] += temp.data
			if temp.left:
				q.append(temp.left)
				l.append(level - 1)
			if temp.right:
				q.append(temp.right)
				l.append(level + 1)
		for i in sorted(dic):
			lis.append(dic[i])
		return lis


class Solution:

	def trav(self, root, dp, cen):
		if root == None:
			return
		if dp.get(cen) == None:
			dp[cen] = 0
		dp[cen] += root.data
		self.trav(root.left, dp, cen - 1)
		self.trav(root.right, dp, cen + 1)

	def verticalSum(self, root):
		dp = dict()
		self.trav(root, dp, 0)
		ans = []
		for x in sorted(dp.keys()):
			ans.append(dp[x])
		return ans


class Solution:

	def verticalSum(self, root):
		if not root:
			return
		q = [[0, root]]
		dicti = {}
		while q:
			for _ in range(len(q)):
				(idx, node) = q.pop(0)
				if idx in dicti:
					dicti[idx].append(node.data)
				else:
					dicti[idx] = [node.data]
				if node.left:
					q.append([idx - 1, node.left])
				if node.right:
					q.append([idx + 1, node.right])
		res = []
		for i in sorted(dicti):
			res.append(sum(dicti[i]))
		return res


from collections import deque

class Solution:

	def verticalSum(self, root):
		res = []
		if not root:
			return res
		queue = deque()
		mp = {}
		queue.append([root, 0])
		while queue:
			sz = len(queue)
			sum = 0
			for _ in range(sz):
				(node, freq) = queue.popleft()
				if freq not in mp:
					mp[freq] = node.data
				else:
					mp[freq] += node.data
				if node.left:
					queue.append([node.left, freq - 1])
				if node.right:
					queue.append([node.right, freq + 1])
		for (k, v) in sorted(mp.items()):
			res.append(v)
		return res


from collections import OrderedDict

class Solution:

	def verticalSum(self, root):
		p = []
		q = []
		p.append(0)
		q.append(root)
		g = {}
		while len(q) > 0:
			a = p.pop(0)
			b = q.pop(0)
			if a not in g:
				g[a] = [b.data]
			else:
				g[a].append(b.data)
			if b.left != None:
				p.append(a - 1)
				q.append(b.left)
			if b.right != None:
				p.append(a + 1)
				q.append(b.right)
		m = OrderedDict(sorted(g.items()))
		ans = []
		for x in m:
			ans.append(sum(m[x]))
		return ans


from collections import defaultdict

class Solution:

	def verticalSum(self, root):
		B = []
		A = []
		self.x(root, A, 0)
		D = {}
		for i in A:
			if i[1] not in D:
				D[i[1]] = i[0]
			else:
				D[i[1]] += i[0]
		for j in sorted(D.keys()):
			B.append(D[j])
		return B

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


class Solution:

	def verticalSum(self, root):
		if root == None:
			return
		q = [[0, root]]
		d = {}
		while q:
			t = q.pop(0)
			if t[0] not in d:
				d[t[0]] = t[1].data
			else:
				d[t[0]] += t[1].data
			if t[1].left:
				q.append([t[0] - 1, t[1].left])
			if t[1].right:
				q.append([t[0] + 1, t[1].right])
		ans = []
		for (i, j) in sorted(d.items()):
			ans.append(j)
		return ans


from collections import OrderedDict

class Solution:

	def verticalSum(self, root):
		q = []
		d = dict()
		q.append((root, 0))
		while len(q) > 0:
			(c, k) = q.pop(0)
			if c and k in d:
				d[k] += c.data
			elif c:
				d[k] = c.data
			if c and c.right:
				q.append((c.right, k + 1))
			if c and c.left:
				q.append((c.left, k - 1))
		res = []
		for i in sorted(d.keys()):
			res.append(d[i])
		return res


class Solution:

	def verticalSum(self, root):
		hash = {}
		l = [0] * 1
		r = [0] * 1

		def fun(root, line):
			if root == None:
				return
			if line < l[0]:
				l[0] = line
			if line > r[0]:
				r[0] = line
			if line not in hash:
				hash[line] = [root.data]
			else:
				hash[line].append(root.data)
			fun(root.left, line - 1)
			fun(root.right, line + 1)
		fun(root, 0)
		ans = []
		for i in range(l[0], r[0] + 1):
			ans.append(sum(hash[i]))
		return ans


class Solution:

	def verticalSum(self, root):
		q = []
		q.append(root)
		aq = []
		d = {}
		aq.append(0)
		d[0] = [root.data]
		while len(q):
			p = q.pop(0)
			dic = aq.pop(0)
			if p.left:
				another = dic - 1
				q.append(p.left)
				aq.append(another)
				if another not in d.keys():
					d[another] = [p.left.data]
				else:
					d[another].append(p.left.data)
			if p.right:
				another = dic + 1
				q.append(p.right)
				aq.append(another)
				if another not in d.keys():
					d[another] = [p.right.data]
				else:
					d[another].append(p.right.data)
		for i in list(d.keys()):
			d[i] = sum(d[i])
		keys = list(d.keys())
		values = list(d.values())
		for i in range(len(keys) - 1):
			for j in range(len(keys) - 1 - i):
				if keys[j] > keys[j + 1]:
					(keys[j], keys[j + 1]) = (keys[j + 1], keys[j])
					(values[j], values[j + 1]) = (values[j + 1], values[j])
		return values


class Solution:

	def verticalSum(self, root):

		def solve(root, dic, cur):
			if root == None:
				return
			if cur in dic:
				dic[cur].append(root.data)
			else:
				dic[cur] = [root.data]
			solve(root.left, dic, cur - 1)
			solve(root.right, dic, cur + 1)
			return dic
		dic = {}
		dicc = solve(root, dic, 0)
		ans = []
		arr = []
		for i in dicc:
			arr.append(i)
		arr.sort()
		for i in arr:
			ans.append(sum(dicc[i]))
		return ans


class Solution:

	def verticalSum(self, root):

		def traversal(root):
			if root == None:
				return None
			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 + 1])
			return list(map(lambda x: x[1], list(sorted(dict1.items(), key=lambda x: x[0]))))
		return traversal(root)


class Solution:

	def verticalSum(self, root):
		mymap = {}
		self.solve(root, 0, mymap)
		res = []
		keys = sorted(mymap)
		for i in keys:
			res.append(mymap[i])
		return res

	def solve(self, root, vertical, mymap):
		if vertical in mymap:
			mymap[vertical] += root.data
		else:
			mymap[vertical] = root.data
		if root.left:
			self.solve(root.left, vertical - 1, mymap)
		if root.right:
			self.solve(root.right, vertical + 1, mymap)


class my_node:

	def __init__(self, num, x):
		self.node = x
		self.number = num

class Solution:

	def verticalSum(self, root):
		f = {}
		q = []
		if root is None:
			return 0
		extra = my_node(0, root)
		q.append(extra)
		q.append('$')
		level = 0
		while len(q) > 0:
			t = q.pop(0)
			if t == '$':
				if len(q) > 0:
					level += 1
					q.append('$')
			else:
				if t.number in f:
					f[t.number].append(t.node.data)
				else:
					f[t.number] = [t.node.data]
				if t.node.left is not None:
					extra = my_node(t.number - 1, t.node.left)
					q.append(extra)
				if t.node.right is not None:
					extra = my_node(t.number + 1, t.node.right)
					q.append(extra)
		final = []
		for i in f:
			f[i] = sum(f[i])
		for i in range(-level, level + 1):
			if i in f:
				final.append(f[i])
		return final


class Solution:

	def verticalSum(self, root):
		if root == None:
			return
		ans = []
		h = {}
		q = [(0, root)]
		while q:
			(x, curr) = q.pop()
			h[x] = h.get(x, 0) + curr.data
			if curr.left:
				q.append((x - 1, curr.left))
			if curr.right:
				q.append((x + 1, curr.right))
		for k in sorted(h.keys()):
			ans.append(h[k])
		return ans


from collections import Counter

class Solution:

	def verticalSum(self, root):
		c = Counter()
		self.myFunc(root, c, 0)
		return [c[item] for item in sorted(c)]

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


class Solution:

	def verticalSum(self, root):
		if not root:
			return
		deque = [(root, 0)]
		mp = {}
		while deque:
			(node, level) = deque.pop()
			mp[level] = mp.get(level, 0) + node.data
			if node.left:
				deque.append((node.left, level - 1))
			if node.right:
				deque.append((node.right, level + 1))
		res = []
		for k in sorted(mp.keys()):
			res.append(mp[k])
		return res


class Solution:

	def verticalSum(self, root):
		res = {}

		def helper(root, n):
			if root == None:
				return
			if n in res:
				res[n] += root.data
			else:
				res[n] = root.data
			helper(root.left, n - 1)
			helper(root.right, n + 1)
		helper(root, 0)
		res = sorted(res.items(), key=lambda kv: (kv[0], kv[1]))
		ans = []
		for ele in res:
			ans.append(ele[1])
		return ans


class Solution:

	def __init__(self):
		import math
		self.hashmap = {}
		self.maxline = -1 * math.inf
		self.minline = math.inf

	def func(self, Node, line):
		if Node == None:
			return
		self.maxline = max(self.maxline, line)
		self.minline = min(self.minline, line)
		if line in self.hashmap:
			self.hashmap[line] += Node.data
		else:
			self.hashmap[line] = Node.data
		self.func(Node.left, line - 1)
		self.func(Node.right, line + 1)

	def verticalSum(self, root):
		self.func(root, 0)
		ans = []
		for i in range(self.minline, self.maxline + 1):
			ans.append(self.hashmap[i])
		return ans


class Solution:

	def verticalSum(self, root):
		if not root:
			return []

		def lvl(root):
			if not root:
				return
			myList = []
			vList = []
			ver = 0
			myList.append([root, ver])
			while len(myList) > 0:
				var = myList.pop(0)
				vList.append([var[0].data, var[1]])
				if var[0].left:
					myList.append([var[0].left, var[1] - 1])
				if var[0].right:
					myList.append([var[0].right, var[1] + 1])
			return vList
		myList = lvl(root)
		myList.sort(key=lambda x: x[1])
		min = myList[0][1]
		vList = []
		for i in range(len(myList)):
			ele = myList[i][1] - min
			if len(vList) > ele:
				vList[ele] += myList[i][0]
			else:
				vList.append(myList[i][0])
		return vList


from collections import defaultdict

class Solution:

	def verticalSum(self, root):
		dic = defaultdict(int)

		def rankMap(root, rank):
			dic[rank] += root.data
			if root.left:
				rankMap(root.left, rank - 1)
			if root.right:
				rankMap(root.right, rank + 1)
		rankMap(root, 0)
		arr = []
		for i in sorted(dic.keys()):
			arr.append(dic[i])
		return arr


class Solution:
	my_dict = {}

	def verticalSum(self, root):
		self.my_dict = {}

		def preorder(rt, i):
			if rt:
				self.my_dict[i] = rt.data + self.my_dict.get(i, 0)
				preorder(rt.left, i - 1)
				preorder(rt.right, i + 1)
			return
		preorder(root, 0)
		res = []
		sorted_keys = sorted(self.my_dict)
		for key in sorted_keys:
			res.append(self.my_dict[key])
		return res


class Solution:

	def verticalSum(self, root):
		d = {}
		res = []

		def helper(rt, d, k):
			if rt:
				if k in d:
					d[k] += rt.data
				else:
					d[k] = rt.data
				helper(rt.left, d, k - 1)
				helper(rt.right, d, k + 1)
			return
		helper(root, d, 0)
		keys = sorted(d)
		for i in keys:
			res.append(d[i])
		return res


class Solution:

	def _init_(self, root):
		self.root = root

	def verticalsumutil(self, root, hd, dict1):
		if root is None:
			return None
		if hd not in dict.keys(dict1):
			dict1[hd] = root.data
		else:
			dict1[hd] += root.data
		if root.left:
			self.verticalsumutil(root.left, hd - 1, dict1)
		if root.right:
			self.verticalsumutil(root.right, hd + 1, dict1)

	def verticalSum(self, root):
		hd = 0
		dict1 = {}
		self.verticalsumutil(root, 0, dict1)
		res = []
		for i in sorted(dict.keys(dict1)):
			res.append(dict1[i])
		return res


class Solution:

	def verticalSum(self, root):
		k = 0
		d = {}
		self.Trav(root, k, d)
		v = list(d.items())
		v.sort(reverse=True)
		x = []
		for i in v:
			x.append(i[1])
		return x

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


class Solution:

	def verticalSum(self, root):

		def solver(root, i=501):
			if not root:
				return
			if ans[i] == None:
				ans[i] = 0
			ans[i] += root.data
			solver(root.left, i - 1)
			solver(root.right, i + 1)
		ans = [None] * 1002
		solver(root)
		return [i for i in ans if i is not None]


import collections

class Solution:

	def verticalSum(self, root):
		if not root:
			return []
		queue = [(root, 0)]
		max_ = 0
		min_ = 0
		ans = []
		map_ = collections.defaultdict(int)
		while len(queue):
			(top, width) = queue.pop(0)
			min_ = min(width, min_)
			max_ = max(width, max_)
			map_[width] += top.data
			if top.left:
				queue.append((top.left, width - 1))
			if top.right:
				queue.append((top.right, width + 1))
		for i in range(min_, max_ + 1):
			ans.append(map_[i])
		return ans


class Solution:

	def verticalSum(self, root):
		if root == None:
			return None
		dicting = dict()
		self.solve(root, 0, dicting)
		myData = [data[1] for data in sorted(dicting.items())]
		return myData

	def solve(self, root, position, dicting):
		if root == None:
			return None
		dicting[position] = dicting.get(position, 0) + root.data
		self.solve(root.left, position - 1, dicting)
		self.solve(root.right, position + 1, dicting)
		return None


class Solution:

	def verticalSum(self, root):
		if root == None:
			return None
		dicting = dict()
		self.solve(root, 0, dicting)
		keys = dicting.keys()
		(min_, max_) = (min(keys), max(keys))
		result = list()
		for key in range(min_, max_ + 1):
			result.append(dicting[key])
		return result

	def solve(self, root, position, dicting):
		if root == None:
			return None
		dicting[position] = dicting.get(position, 0) + root.data
		self.solve(root.left, position - 1, dicting)
		self.solve(root.right, position + 1, dicting)
		return None


class Solution:

	def verticalSum(self, root):
		d = {}
		level = 0
		if not root:
			return 0
		helper1(root, level, d)
		l = []
		d1 = sorted(d.keys())
		for i in d1:
			l.append(sum(d[i]))
		return l

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


class TNode:

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

class LLNode:

	def __init__(self, key):
		self.key = key
		self.prev = None
		self.next = None

def verticalSumDLLUtil(root: TNode, sumNode: LLNode):
	sumNode.key = sumNode.key + root.data
	if root.left:
		if sumNode.prev == None:
			sumNode.prev = LLNode(0)
			sumNode.prev.next = sumNode
		verticalSumDLLUtil(root.left, sumNode.prev)
	if root.right:
		if sumNode.next == None:
			sumNode.next = LLNode(0)
			sumNode.next.prev = sumNode
		verticalSumDLLUtil(root.right, sumNode.next)

def verticalSumDLL(root: TNode):
	ans = []
	sumNode = LLNode(0)
	verticalSumDLLUtil(root, sumNode)
	while sumNode.prev != None:
		sumNode = sumNode.prev
	while sumNode != None:
		ans.append(sumNode.key)
		sumNode = sumNode.next
	return ans

class Solution:

	def verticalSum(self, root):
		return verticalSumDLL(root)


class Solution:

	def verticalOrder(self, root):
		if not root:
			return
		output = []
		q = []
		d = {}
		maxx = -1 * 10 ** 8
		minn = 10 ** 8
		q.append([root, 0])
		while q:
			front = q[0]
			q.pop(0)
			maxx = max(maxx, front[1])
			minn = min(minn, front[1])
			if front[1] in d:
				d[front[1]].append(front[0].data)
			else:
				d[front[1]] = [front[0].data]
			if front[0].left:
				q.append([front[0].left, front[1] - 1])
			if front[0].right:
				q.append([front[0].right, front[1] + 1])
		for i in range(minn, maxx + 1, 1):
			temp = d[i]
			output.append(temp)
		return output

	def verticalSum(self, root):
		ans = []
		result = self.verticalOrder(root)
		for i in result:
			ans.append(sum(i))
		return ans


class Solution:

	def verticalSum(self, root):
		q = [(root, 0)]
		hash = dict()
		minw = maxw = 0
		ans = []
		while q:
			(x, w) = q.pop(0)
			hash[w] = hash.get(w, 0) + x.data
			minw = min(minw, w)
			maxw = max(maxw, w)
			if x.left:
				q.append((x.left, w - 1))
			if x.right:
				q.append((x.right, w + 1))
		for i in range(minw, maxw + 1):
			ans.append(hash[i])
		return ans


class Solution:

	def verticalSum(self, root):
		dict_ = dict()

		def func(node, i):
			if not node:
				return
			if i not in dict_:
				dict_[i] = 0
			dict_[i] += node.data
			func(node.left, i - 1)
			func(node.right, i + 1)
		func(root, 0)
		ans = []
		for i in sorted(dict_.keys()):
			ans.append(dict_[i])
		return ans


class Solution:

	def helper(self, root, dist, ver_sum):
		if root is None:
			return
		if dist in ver_sum.keys():
			ver_sum[dist] += root.data
		else:
			ver_sum[dist] = root.data
		self.helper(root.left, dist - 1, ver_sum)
		self.helper(root.right, dist + 1, ver_sum)

	def verticalSum(self, root):
		ver_sum = {}
		self.helper(root, 0, ver_sum)
		sorted_list = sorted(ver_sum.items())
		res = []
		for i in sorted_list:
			res.append(i[1])
		return res


class Solution:

	def verticalSum(self, root):

		def helper(root, mp, k):
			if root:
				if k in mp:
					mp[k] += root.data
				else:
					mp[k] = root.data
				helper(root.left, mp, k + 1)
				helper(root.right, mp, k - 1)
		if not root:
			return []
		mp = {}
		res = []
		helper(root, mp, 0)
		k = list(mp.keys())
		k.sort()
		for i in k:
			res.append(mp[i])
		return res[::-1]


class Solution:

	def util(self, root, path_num, mp):
		if not root:
			return
		self.util(root.left, path_num - 1, mp)
		mp[path_num] = mp.get(path_num, 0) + root.data
		self.util(root.right, path_num + 1, mp)

	def verticalSum(self, root):
		mp = {}
		self.util(root, 0, mp)
		r = []
		for i in sorted(mp.keys()):
			r.append(mp[i])
		return r


class Solution:

	def verticalSum(self, root):

		def helper(root):
			d = {}
			q = deque()
			if not root:
				return None
			q.append([root, 0])
			d[0] = root.data
			while q:
				for i in range(len(q)):
					a = q.popleft()
					if a[0].left:
						q.append([a[0].left, a[1] - 1])
					if a[0].right:
						q.append([a[0].right, a[1] + 1])
				for i in q:
					b = i[0].data
					c = i[1]
					if c not in d:
						d[c] = b
					else:
						d[c] += b
			data_range = []
			for i in d:
				data_range.append(i)
			data_range.sort()
			ans = []
			for i in data_range:
				ans.append(d[i])
			return ans
		return helper(root)


class Solution:

	def verticalSum(self, root):

		def vertical(root, hd, m):
			if root is None:
				return
			try:
				m[hd].append(root.data)
			except:
				m[hd] = [root.data]
			vertical(root.left, hd - 1, m)
			vertical(root.right, hd + 1, m)
		m = {}
		hd = 0
		vertical(root, hd, m)
		a = []
		for i in sorted(m):
			Sum = sum(m[i])
			a.append(Sum)
		return a


class Solution:

	def verticalSum(self, root):

		def vertical(root, hd, m):
			if root is None:
				return
			try:
				m[hd].append(root.data)
			except:
				m[hd] = [root.data]
			vertical(root.left, hd - 1, m)
			vertical(root.right, hd + 1, m)
		m = {}
		hd = 0
		vertical(root, hd, m)
		a = []
		for i in m:
			if i - 1 not in m:
				j = 0
				while j < len(m):
					Sum = sum(m[i + j])
					a.append(Sum)
					j += 1
		return a


class Solution:

	def __init__(self):
		self.map = dict()
		self.res = []

	def verticalSum(self, root):
		d = {}

		def helper(root, hd):
			if not root:
				return
			if hd in d:
				d[hd] = d[hd] + root.data
			else:
				d[hd] = root.data
			helper(root.left, hd - 1)
			helper(root.right, hd + 1)
		helper(root, 0)
		ans = []
		for (i, j) in sorted(d.items()):
			ans.append(j)
		return ans


from collections import defaultdict

class Solution:

	def verticalSum(self, root):
		d = defaultdict(list)

		def helper(root, d, hd):
			if not root:
				return
			if hd in d:
				d[hd].append(root.data)
			else:
				d[hd].append(root.data)
			helper(root.left, d, hd - 1)
			helper(root.right, d, hd + 1)
		helper(root, d, 0)
		ans = []
		for (i, j) in sorted(d.items()):
			ans.append(j)
		finalans = []
		for i in ans:
			finalans.append(sum(i))
		return finalans


from collections import defaultdict, deque

class Solution:

	def leveOrderTraversal(self, myans, root):
		if not root:
			return
		queue = deque()
		queue.append([root, 0, 0])
		while len(queue) != 0:
			data = queue.popleft()
			Node = data[0]
			VarticalNumber = data[1]
			levelNumber = data[2]
			myans[VarticalNumber].append((levelNumber, Node.data))
			if Node.left:
				queue.append([Node.left, VarticalNumber - 1, levelNumber + 1])
			if Node.right:
				queue.append([Node.right, VarticalNumber + 1, levelNumber + 1])

	def verticalSum(self, root):
		myans = defaultdict(list)
		self.leveOrderTraversal(myans, root)
		varticals = list(myans.keys())
		varticals.sort()
		ans = []
		for i in varticals:
			temp = []
			for val in sorted(myans[i]):
				temp.append(val[1])
			ans.append(temp)
		finalans = []
		for i in ans:
			finalans.append(sum(i))
		return finalans


class Solution:

	def verticalSum(self, root):
		val_m = {}

		def getSum(root, index):
			if root == None:
				return
			getSum(root.left, index - 1)
			getSum(root.right, index + 1)
			if index in val_m:
				val_m[index] += root.data
			else:
				val_m[index] = root.data
		getSum(root, 0)
		s_val = sorted(val_m.items())
		result = []
		for (key, val) in s_val:
			result.append(val)
		return result


from collections import defaultdict

class Solution:

	def verticalSum(self, root):
		d = defaultdict(list)

		def dfs(root, d, width):
			if not root:
				return
			d[width].append(root.data)
			dfs(root.left, d, width - 1)
			dfs(root.right, d, width + 1)
		dfs(root, d, 0)
		ans = []
		for vals in sorted(d.keys()):
			ans.append(sum(d[vals]))
		return ans


class Solution:

	def verticalSum(self, root):
		if root is None:
			return
		mp = {}
		res = []
		self.verticalHelper(root, 0, mp)
		min_int = float('inf')
		max_int = float('-inf')
		for i in mp.keys():
			if i < min_int:
				min_int = i
			if i > max_int:
				max_int = i
		for i in range(min_int, max_int + 1):
			res.append(mp[i])
		return res

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


class Solution:

	def verticalSum(self, root):
		dic = {}

		def dfs(root, c):
			if not root:
				return
			if c not in dic:
				dic[c] = root.data
			else:
				dic[c] += root.data
			dfs(root.left, c - 1)
			dfs(root.right, c + 1)
		dfs(root, 0)
		ans = []
		for i in sorted(dic.keys()):
			ans.append(dic[i])
		return ans


class Solution:

	def verticalSum(self, root):

		def InOrder(root, myDict, hd):
			if not root:
				return
			InOrder(root.left, myDict, hd - 1)
			if hd in myDict.keys():
				myDict[hd] = myDict[hd] + root.data
			else:
				myDict[hd] = root.data
			InOrder(root.right, myDict, hd + 1)
		(myList, myDict) = ([], {})
		InOrder(root, myDict, 0)
		for i in sorted(myDict.keys()):
			myList.append(myDict[i])
		return myList


import sys

class Solution:

	def __init__(self) -> None:
		self.vertical_sums = {}
		self.max_level = -sys.maxsize
		self.min_level = sys.maxsize

	def preOrder(self, root, vert_level):
		if not root:
			return
		self.max_level = max(self.max_level, vert_level)
		self.min_level = min(self.min_level, vert_level)
		self.vertical_sums[vert_level] = self.vertical_sums.get(vert_level, 0) + root.data
		self.preOrder(root.left, vert_level - 1)
		self.preOrder(root.right, vert_level + 1)

	def verticalSum(self, root):
		self.preOrder(root, 0)
		ans = []
		for vert_level in range(self.min_level, self.max_level + 1):
			ans.append(self.vertical_sums[vert_level])
		return ans


class Solution:

	def verticalSum(self, root):
		hash = {}
		q = [(0, root)]
		while q:
			cur = q.pop(0)
			if cur[0] in hash:
				hash[cur[0]] += cur[1].data
			else:
				hash[cur[0]] = cur[1].data
			if cur[1].left:
				q.append((cur[0] - 1, cur[1].left))
			if cur[1].right:
				q.append((cur[0] + 1, cur[1].right))
		res = []
		for (key, val) in sorted(hash.items()):
			res.append(val)
		return res


class Solution:

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

	def verticalSum(self, root):

		def vSumR(root, hd):
			if not root:
				return
			vSumR(root.left, hd - 1)
			try:
				self.mp[hd] += root.data
			except KeyError:
				self.mp[hd] = root.data
			vSumR(root.right, hd + 1)
		vSumR(root, 0)
		ans = []
		for i in sorted(self.mp.keys()):
			ans.append(self.mp[i])
		return ans


class Solution:

	def verticalSum(self, root):
		dic = {}
		hd = 0
		k = []
		self.summ(root, hd, dic)
		for (i, j) in sorted(dic.items()):
			k.append(j)
		return k

	def summ(self, root, hd, dic):
		if root == None:
			return
		if hd in dic:
			dic[hd] = dic[hd] + root.data
		else:
			dic[hd] = root.data
		self.summ(root.left, hd - 1, dic)
		self.summ(root.right, hd + 1, dic)
		return dic


from collections import OrderedDict

class Solution:

	def func(self, root, key, hashm):
		if root:
			hashm[key] = hashm.get(key, 0) + root.data
			self.func(root.left, key - 1, hashm)
			self.func(root.right, key + 1, hashm)

	def verticalSum(self, root):
		hashm = {}
		key = 0
		self.func(root, 0, hashm)
		keys = sorted(hashm)
		ans = []
		for k in keys:
			ans.append(hashm[k])
		return ans


from collections import defaultdict as dd

class Solution:

	def verticalSum(self, root):

		def dfs(root, hd):
			if root is None:
				return
			d[hd] += [root.data]
			dfs(root.left, hd - 1) or dfs(root.right, hd + 1)
		d = dd(list)
		l = []
		dfs(root, 0)
		for i in sorted(d.keys()):
			l.append(sum(d[i]))
		return l


from collections import defaultdict

class Solution:

	def verticalSum(self, root):
		sums = defaultdict(int)
		min_max = [0, 0]

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


class Solution:

	def verticalSum(self, root):
		d = self.findVS(root, {}, 0)
		l = []
		for values in sorted(d.keys()):
			l.append(d[values])
		return l

	def findVS(self, root, d, i):
		if root is None:
			return
		if i in d:
			d[i] += root.data
		else:
			d[i] = root.data
		self.findVS(root.left, d, i - 1)
		self.findVS(root.right, d, i + 1)
		return d


class Solution:

	def verticle(self, root, hd, d):
		if root is None:
			return
		self.verticle(root.left, hd - 1, d)
		if d.get(hd) is None:
			prevsum = 0
		else:
			prevsum = d.get(hd)
		d[hd] = prevsum + root.data
		self.verticle(root.right, hd + 1, d)

	def verticalSum(self, root):
		res = []
		if root is None:
			return res
		d = dict()
		self.verticle(root, 0, d)
		k = list(d.keys())
		k.sort()
		for i in k:
			res.append(d[i])
		return res


class Node:

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

class Solution:

	def verticalSum(self, root):
		d = {}
		l = []
		self.fn(root, 0, 0, d)
		keys = sorted(d.keys())
		for key in keys:
			count = 0
			for j in d[key]:
				count += j[0]
			l.append(count)
		return l

	def fn(self, root, ht, dist, d):
		if root:
			if dist in d:
				d[dist] += [(root.data, ht)]
			else:
				d[dist] = [(root.data, ht)]
			self.fn(root.left, ht + 1, dist - 1, d)
			self.fn(root.right, ht + 1, dist + 1, d)


class Solution:

	def temp(self, root, v, d):
		if root == None:
			return
		self.temp(root.left, v - 1, d)
		if d.get(v) == None:
			s = 0
		else:
			s = d.get(v)
		d[v] = s + root.data
		self.temp(root.right, v + 1, d)

	def verticalSum(self, root):
		ans = []
		if root == None:
			return ans
		d = {}
		self.temp(root, 0, d)
		k = [k for k in d.keys()]
		k.sort()
		for i in k:
			ans.append(d[i])
		return ans


from collections import OrderedDict

class Solution:

	def buildLineDict(root):
		lineDict = OrderedDict()
		Solution.traversalStep(root, lineDict, 0)
		return lineDict

	def traversalStep(node, myDict, howRight):
		if node != None:
			Solution.traversalStep(node.left, myDict, howRight - 1)
			if myDict.get(howRight) == None:
				myDict[howRight] = 0
			myDict[howRight] += node.data
			Solution.traversalStep(node.right, myDict, howRight + 1)

	def verticalSum(self, root):
		lineDict = Solution.buildLineDict(root)
		newArr = []
		for (_, x) in sorted(lineDict.items()):
			newArr.append(x)
		return newArr


class Solution:

	def verticalSum(self, root):
		m = 999999
		n = -999999
		q = [[root, 0]]
		s = {}
		c = 0
		while c != len(q):
			t = q[c][0]
			g = q[c][1]
			if g in s:
				s[g] += t.data
			else:
				s[g] = t.data
			if g > n:
				n = g
			if g < m:
				m = g
			if t.left:
				q.append([t.left, g - 1])
			if t.right:
				q.append([t.right, g + 1])
			c += 1
		l = []
		for i in range(m, n + 1):
			l.append(s[i])
		return l


class Solution:

	def verticalSum(self, root):

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


from queue import Queue

class Solution:

	def __init__(self):
		self.dictt = dict()

	def verticalSum(self, root):
		self.solve(root)
		myData = [data[1] for data in sorted(self.dictt.items())]
		return myData

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


class Solution:

	def inorder(self, root, d, vl):
		if root:
			if vl in d:
				d[vl] += root.data
			else:
				d[vl] = root.data
			self.inorder(root.left, d, vl - 1)
			self.inorder(root.right, d, vl + 1)

	def verticalSum(self, root):
		d = dict()
		self.inorder(root, d, 0)
		ans = []
		for (i, j) in sorted(d.items()):
			ans.append(j)
		return ans


class Solution:

	def verticalSum(self, root):
		from collections import defaultdict
		d = defaultdict(list)

		def traverse(root, pos):
			if root == None:
				return
			d[pos].append(root.data)
			traverse(root.left, pos - 1)
			traverse(root.right, pos + 1)
		traverse(root, 0)
		res = []
		for i in sorted(d.keys()):
			res.append(sum(d[i]))
		return res


class Solution:

	def verticalSum(self, root):
		dict = {}
		res = []

		def buildDict(root, i):
			if not root:
				return None
			buildDict(root.left, i - 1)
			if i in dict:
				dict[i] += root.data
			else:
				dict[i] = root.data
			buildDict(root.right, i + 1)
		buildDict(root, 0)
		for (i, j) in sorted(dict.items()):
			res.append(j)
		return res


class Solution:

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

	def verticalSum(self, root):

		def f(root, h):
			if root == None:
				return
			if h in self.d.keys():
				self.d[h] += root.data
			else:
				self.d[h] = root.data
			f(root.left, h - 1)
			f(root.right, h + 1)
		f(root, 0)
		res = []
		for i in sorted(self.d.keys()):
			res.append(self.d[i])
		return res