Given a Binary Search Tree with unique node values and a target value. You have to find the node whose data is equal to target and return the sum of all descendant (of target) node's data which are vertically below the target node. Initially, you are at the root node.
Note: If target node is not present in bst then return -1.
Example 1:
Input:
Target = 35
Output: 32
Explanation: Vertically below 35 is 32.
Example 2:
Input:
Target = 25
Output: 52
Explanation: Vertically below 25 is 22, 30 and their sum is 52.
Your Task:
You don't need to read input or print anything. Your task is to complete the function verticallyDownBST() which takes BST(you are given root node of bst ) and target as input, and return an interger value as the sum of vertically down nodes from target. If target is not present in bst then return -1.
Expected Time Complexity: O( n ), n is number of nodes.
Expected Auxiliary Space: O(Height of the tree).
Constraints:
1 <= n < 10^{6}
1 <= target <= n
1 <= node.data < 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Range queries

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self,val):

        self.data=val

        self.left=None

        self.right=None

'''



class Solution:

    def verticallyDownBST(self, root, target):

        #code here

Solutions:
from collections import deque

class Solution:

	def find(self, root, target):
		node = root
		while node:
			if node.data == target:
				return node
			elif target < node.data:
				node = node.left
			else:
				node = node.right
		return node

	def get_sum_of_descendants(self, root):
		q = deque()
		q.append((root, 0))
		desc_sum = 0
		while q:
			(node, rank) = q.popleft()
			if node is None:
				continue
			if rank == 0:
				desc_sum += node.data
			q.extend([(node.left, rank - 1), (node.right, rank + 1)])
		return desc_sum - root.data

	def verticallyDownBST(self, root, target):
		node = self.find(root, target)
		if node is None:
			return -1
		desc_sum = self.get_sum_of_descendants(node)
		return desc_sum


class Solution:

	def verticallyDownBST(self, root, target):
		return self.dfs(root, target, False, 0, 0) - 1

	def dfs(self, r, targetValue, hasFound, targetPos, currPos):
		if r is None:
			return 0
		s = 0
		if hasFound and targetPos == currPos:
			s += r.data
		elif r.data == targetValue:
			hasFound = True
			targetPos = currPos
			s += 1
		s += self.dfs(r.left, targetValue, hasFound, targetPos, currPos - 1)
		s += self.dfs(r.right, targetValue, hasFound, targetPos, currPos + 1)
		return s


class Solution:

	def __init__(self):
		self.flag = False
		self.ans = 0
		self.g = 0
		self.start = None

	def dfs(self, root, trt, gg):
		if root is None:
			return
		if root.data == trt and (not self.flag):
			self.g = gg
			self.start = root
			return
		self.dfs(root.left, trt, gg - 1)
		self.dfs(root.right, trt, gg + 1)
		if self.flag:
			if self.g == gg:
				self.ans += root.data

	def verticallyDownBST(self, root, target):
		self.dfs(root, target, 0)
		self.flag = True
		if self.start is None:
			return -1
		self.dfs(self.start, target, self.g)
		return self.ans - self.start.data


class Solution:

	def verticallyDownBST(self, root, target):

		def helper(root, x):
			ans = 0
			if root is None:
				return 0
			if x == 0:
				ans = root.data
			ans += helper(root.left, x - 1)
			ans += helper(root.right, x + 1)
			return ans

		def find(root, target):
			if root is None:
				return -1
			if root.data == target:
				return root
			if root.data > target:
				return find(root.left, target)
			return find(root.right, target)
		node = find(root, target)
		if node == -1:
			return -1
		return helper(node, 0) - target


class Solution:

	def verticallyDownBST(self, root, target):

		def dfs(node, variance):
			if not node:
				return 0
			if variance == 0:
				if not node.left and (not node.right):
					return node.data
				if node.right and node.left:
					return dfs(node.right, 1) + dfs(node.left, -1) + node.data
				elif node.left:
					return dfs(node.left, -1) + node.data
				else:
					return dfs(node.right, 1) + node.data
			else:
				if not node.left and (not node.right):
					return 0
				if node.left and node.right:
					return dfs(node.left, variance - 1) + dfs(node.right, variance + 1)
				elif node.left:
					return dfs(node.left, variance - 1)
				else:
					return dfs(node.right, variance + 1)
		tar_node = root
		while tar_node and tar_node.data != target:
			if tar_node.data > target:
				tar_node = tar_node.left
			else:
				tar_node = tar_node.right
		if not tar_node:
			return -1
		return dfs(tar_node, 0) - tar_node.data


class Solution:

	def verticallyDownBST(self, root, target):

		def down(node, direction):
			nonlocal res
			if node:
				if direction == 0:
					res += node.data
				down(node.left, direction - 1)
				down(node.right, direction + 1)

		def find(node, target):
			nonlocal target_node
			if target_node == None:
				if node:
					if node.data > target:
						find(node.left, target)
					elif node.data < target:
						find(node.right, target)
					else:
						target_node = node
						down(node, 0)
		res = -target
		target_node = None
		find(root, target)
		if res == -target:
			return -1
		return res


class Solution:

	def searchTarget(self, root, target):
		if root == None:
			return -1
		if root.data == target:
			return root
		if root.data > target:
			return self.searchTarget(root.left, target)
		else:
			return self.searchTarget(root.right, target)

	def verticalSum(self, root, temp, sum_):
		if root.left != None:
			if temp - 1 == 0:
				sum_[0] = sum_[0] + root.left.data
			self.verticalSum(root.left, temp - 1, sum_)
		if root.right != None:
			if temp + 1 == 0:
				sum_[0] = sum_[0] + root.right.data
			self.verticalSum(root.right, temp + 1, sum_)

	def verticallyDownBST(self, root, target):
		node = self.searchTarget(root, target)
		if node == -1:
			return -1
		sum_ = [0]
		self.verticalSum(node, 0, sum_)
		return sum_[0]


import sys
sys.setrecursionlimit(1000000)

class Solution:

	def __init__(self):
		self.answer = -1
		self.target_position = 0
		self.start_node = None
		self.total = 0

	def findTarget(self, root, target, target_position):
		if root is None:
			return
		if root.data == target:
			self.target_position = target_position
			self.start_node = root
			return
		elif root.data < target:
			self.findTarget(root.right, target, target_position + 1)
		else:
			self.findTarget(root.left, target, target_position - 1)

	def findVertical(self, start_node, current_position):
		if start_node is None:
			return
		if current_position == self.target_position:
			self.total += start_node.data
		self.findVertical(start_node.right, current_position + 1)
		self.findVertical(start_node.left, current_position - 1)

	def verticallyDownBST(self, root, target):
		self.findTarget(root, target, 0)
		if self.start_node is None:
			return -1
		curr = self.target_position
		self.findVertical(self.start_node.right, curr + 1)
		self.findVertical(self.start_node.left, curr - 1)
		return self.total


class Solution:

	def findTarget(self, root, target, roott):
		if root is None:
			return
		self.findTarget(root.left, target, roott)
		if root.data == target:
			roott.append(root)
		self.findTarget(root.right, target, roott)

	def traverseDown(self, root, level, target):
		if root is None:
			return
		if level == 0 and root.data != target:
			self.sum += root.data
		self.traverseDown(root.left, level - 1, target)
		self.traverseDown(root.right, level + 1, target)

	def verticallyDownBST(self, root, target):
		roott = []
		level = 0
		self.sum = 0
		self.findTarget(root, target, roott)
		if roott:
			self.traverseDown(roott[0], level, target)
			return self.sum
		else:
			return -1


class Solution:

	def findVerticalSum(self, root, pos, sum):
		if root is None:
			return 0
		sum += self.findVerticalSum(root.left, pos - 1, sum) + self.findVerticalSum(root.right, pos + 1, sum)
		if pos == 0:
			sum += root.data
		return sum

	def solve(self, root, target):
		if root is None:
			return -1
		if root.data == target:
			return self.findVerticalSum(root, 0, 0) - root.data
		(x, y) = (-1, -1)
		if root.data < target:
			x = self.solve(root.right, target)
		else:
			y = self.solve(root.left, target)
		return max(x, y)

	def verticallyDownBST(self, root, target):
		return self.solve(root, target)


class Solution:

	def verticallyDownBST(self, root, tar):

		def helper(node, data):
			if not node:
				return 0
			ans = 0
			if data == 0:
				ans += node.data
			ans += helper(node.left, data - 1) + helper(node.right, data + 1)
			return ans

		def find(node):
			if not node:
				return
			if node.data > tar:
				find(node.left)
			elif node.data < tar:
				find(node.right)
			else:
				self.node = node
			return
		self.node = None
		find(root)
		if self.node == None:
			return -1
		return helper(self.node.left, -1) + helper(self.node.right, 1)


class Solution:

	def __init__(self):
		self.s = 0

	def verticallyDownBST(self, root, target):
		return self.findsum(root, target, 0, None, False)

	def findsum(self, root, target, s, pos, takeNode):
		root = self.getNode(root, target, s, pos)
		if root == None:
			return -1
		return self.getNodetoadd(root, target, s, 0)

	def getNode(self, root, target, s, pos):
		if root == None:
			return
		if root.data == target:
			pos = 0
			return root
		x = self.getNode(root.left, target, s, pos)
		y = self.getNode(root.right, target, s, pos)
		if x:
			return x
		else:
			return y

	def getNodetoadd(self, root, target, s, pos):
		if root == None:
			return
		if pos == 0 and root.data != target:
			self.s += root.data
		x = self.getNodetoadd(root.left, target, self.s, pos - 1)
		y = self.getNodetoadd(root.right, target, self.s, pos + 1)
		return self.s


class Solution:

	def verticallyDownBST(self, root, target):
		if root is None:
			return -1
		if target < root.data:
			return self.verticallyDownBST(root.left, target)
		if target > root.data:
			return self.verticallyDownBST(root.right, target)
		return self.helper(root, 0) - root.data

	def helper(self, root, width):
		if root is None:
			return 0
		output = 0
		if width == 0:
			output += root.data
		output += self.helper(root.left, width - 1)
		output += self.helper(root.right, width + 1)
		return output


from collections import deque

class Solution:

	def verticallyDownBST(self, root, target):
		targetnode = [0]

		def find(root):
			if targetnode[0] != 0:
				return
			if root == None:
				return
			if root.data == target:
				targetnode[0] = root
				return
			if target > root.data:
				find(root.right)
			else:
				find(root.left)
		find(root)
		hm = defaultdict(list)
		q = deque()
		q.append((targetnode[0], 0))
		if targetnode[0] == 0:
			return -1
		while q:
			nc = len(q)
			if nc == 0:
				break
			while nc > 0:
				(node, x) = q.popleft()
				hm[x].append(node.data)
				if node.left:
					q.append((node.left, x - 1))
				if node.right:
					q.append((node.right, x + 1))
				nc -= 1
		return sum(hm[0]) - targetnode[0].data


class Solution:

	def verticallyDownBST(self, root, target):
		l = []

		def findColumn(root, target, l, v, level):
			if root == None:
				return
			if root.data == target:
				l.append(v)
				l.append(level)
				l.append(root)
				return
			findColumn(root.left, target, l, v - 1, level + 1)
			findColumn(root.right, target, l, v + 1, level + 1)
		findColumn(root, target, l, 0, 0)
		if len(l) == 0:
			return -1
		v = l[0]
		level = l[1]
		root1 = l[2]

		def findSum(root, v, column, tlevel, level):
			if root == None:
				return 0
			if column == v and root.data != target:
				return root.data + findSum(root.left, v, column - 1, tlevel, level + 1) + findSum(root.right, v, column + 1, tlevel, level + 1)
			return findSum(root.left, v, column - 1, tlevel, level + 1) + findSum(root.right, v, column + 1, tlevel, level + 1)
		return findSum(root1, 0, 0, level, 0)


class Solution:

	def findTarget(self, root, target):
		temp = root
		while temp:
			if temp.data == target:
				break
			elif temp.data < target:
				temp = temp.right
			else:
				temp = temp.left
		if temp is None:
			return -1
		n = 0
		total = []
		self.POTD(temp, n, total)
		return sum(total) - temp.data

	def POTD(self, root, n, ans):
		if root is None:
			return
		if n == 0:
			ans.append(root.data)
		if root.left:
			self.POTD(root.left, n - 1, ans)
		if root.right:
			self.POTD(root.right, n + 1, ans)

	def verticallyDownBST(self, root, target):
		temp = self.findTarget(root, target)
		return temp


class Solution:

	def __init__(self):
		self.res = -1
		self.s = 0

	def check(self, a, r, k):
		if a == None:
			return 0
		o = self.check(a.left, r - 1, k)
		p = self.check(a.right, r + 1, k)
		if a.data == k:
			self.res = a
		return o + p + a.data

	def io(self, a, r, k):
		if a == None:
			return
		if a.data != k and r == 0:
			self.s += a.data
		self.io(a.left, r - 1, k)
		self.io(a.right, r + 1, k)

	def verticallyDownBST(self, root, target):
		self.check(root, 0, target)
		if self.res == -1:
			return -1
		self.io(self.res, 0, target)
		return self.s


class Solution:

	def dfs(self, root, targetValue, hasFound=False, targetPos=0, currPos=0):
		if root is None:
			return 0
		ans = 0
		if hasFound and targetPos == currPos:
			ans += root.data
		if not hasFound and root.data == targetValue:
			hasFound = True
			targetPos = currPos
			ans += 1
		ans += self.dfs(root.left, targetValue, hasFound, targetPos, currPos - 1)
		ans += self.dfs(root.right, targetValue, hasFound, targetPos, currPos + 1)
		return ans

	def verticallyDownBST(self, root, target):
		return self.dfs(root, target) - 1


import collections

class Solution:

	def verticallyDownBST(self, root, target):
		flag = -1
		queue = collections.deque([[root, 0]])
		(flag, su) = self.traverse(root, queue, flag, target)
		if flag == -1:
			return flag
		return su

	def traverse(self, root, queue, flag, target):
		su = 0
		key = -1
		while queue:
			n = len(queue)
			temp_flag = flag
			while n:
				temp = queue.popleft()
				ptr = temp[0]
				we = temp[1]
				if temp_flag == 1:
					if k == we:
						su += ptr.data
				if ptr.data == target:
					queue = collections.deque([])
					flag = 1
					k = we
				if ptr.left:
					queue.append([ptr.left, we - 1])
				if ptr.right:
					queue.append([ptr.right, we + 1])
				if flag == 1:
					break
				n -= 1
		return (flag, su)


class Solution:

	def verticallyDownBST(self, root, target):

		def helper(root, x):
			if root is None:
				return 0
			count = 0
			if x == 0:
				count += root.data
			count += helper(root.left, x - 1)
			count += helper(root.right, x + 1)
			return count
		if root is None:
			return -1
		if root.data == target:
			count = helper(root, 0)
			return count - root.data
		if target < root.data:
			return self.verticallyDownBST(root.left, target)
		else:
			return self.verticallyDownBST(root.right, target)


class Solution:

	def search(self, root, target):
		if root == None:
			return None
		if root.data == target:
			return root
		if root.data < target:
			return self.search(root.right, target)
		if root.data > target:
			return self.search(root.left, target)

	def descendant(self, root, pos):
		if root != None:
			if pos == 0:
				self.sum += root.data
			self.descendant(root.left, pos - 1)
			self.descendant(root.right, pos + 1)

	def verticallyDownBST(self, root, target):
		k = self.search(root, target)
		if k == None:
			return -1
		(left, right, sum, flag) = (k.left, k.right, 0, True)
		self.sum = -1 * k.data
		self.descendant(k, 0)
		return self.sum


ping = None

class Solution:

	def fun(self, root, level, ans):
		if root:
			if level == 0:
				ans += root.data
			ans = self.fun(root.left, level - 1, ans)
			ans = self.fun(root.right, level + 1, ans)
		return ans

	def check(self, root, target):
		global ping
		if not root:
			return
		if root.data == target:
			ping = root
			return
		self.check(root.left, target)
		self.check(root.right, target)
		return

	def verticallyDownBST(self, root, target):
		global ping
		ans = 0
		if not root:
			return -1
		self.check(root, target)
		if ping:
			ans = self.fun(ping, 0, ans)
			ans -= ping.data
		else:
			return -1
		ping = None
		return ans


class Solution:

	def verticallyDownBST(self, root, target):
		tmp = root
		found = False
		y = 0
		while tmp:
			if target == tmp.data:
				found = True
				break
			elif target < tmp.data:
				y -= 1
				tmp = tmp.left
			else:
				y += 1
				tmp = tmp.right
		if not found:
			return -1
		self.sum = 0
		self.getSum(tmp, y, y)
		return self.sum - target

	def getSum(self, root, y, dir):
		if root == None:
			return
		if y == dir:
			self.sum += root.data
		self.getSum(root.left, y - 1, dir)
		self.getSum(root.right, y + 1, dir)
		return


class Solution:

	def verticallyDownBST(self, root, target):
		x = []
		Solution.target(root, target, x)
		if len(x) == 0:
			return -1
		sum = []
		Solution.bst(x[0], 0, sum)
		s = 0
		for i in sum:
			s += i
		return s - x[0].data

	def bst(root, st, sum):
		if root == None:
			return
		if st == 0:
			sum.append(root.data)
		Solution.bst(root.left, st - 1, sum)
		Solution.bst(root.right, st + 1, sum)

	def target(root, target, x):
		if root.data == target:
			x.append(root)
			return
		if root.left != None:
			Solution.target(root.left, target, x)
		if root.right != None:
			Solution.target(root.right, target, x)


class Solution:

	def findTarget(self, head, target):
		while head is not None:
			if head.data == target:
				return head
			if head.data < target:
				head = head.right
			else:
				head = head.left
		return None

	def rec(self, node, pos):
		sum = 0
		if node is None:
			return sum
		if pos == 0:
			sum = node.data
		if node.left is not None:
			sum = sum + self.rec(node.left, pos - 1)
		if node.right is not None:
			sum = sum + self.rec(node.right, pos + 1)
		return sum

	def verticallyDownBST(self, root, target):
		pTarget = self.findTarget(root, target)
		if pTarget is None:
			return -1
		else:
			return self.rec(pTarget, 0) - target


class Solution:

	def search(self, node, target):
		if self.found:
			return
		if node.data == target:
			self.found = node
			return
		if node.left:
			self.search(node.left, target)
		if node.right:
			self.search(node.right, target)

	def trav(self, node, index):
		if index == 0:
			self.sum += node.data
		if node.left:
			self.trav(node.left, index - 1)
		if node.right:
			self.trav(node.right, index + 1)

	def verticallyDownBST(self, root, target):
		self.found = None
		self.search(root, target)
		if not self.found:
			return -1
		self.sum = -self.found.data
		self.trav(self.found, 0)
		return self.sum


from collections import deque

class Solution:

	def verticallyDownBST(self, root, t):
		flag = False
		d = deque()
		ans = [0, 0, -1]
		d.append([root, 0, 0])
		d.append(-1)
		while len(d) != 1:
			while d[0] != -1:
				cnode = d.popleft()
				if flag and cnode[1] == ans[1]:
					ans[0] = ans[0] + cnode[0].data
				if cnode[0].data == t:
					flag = True
					ans = [0, cnode[1]]
					while len(d) != 0:
						d.popleft()
					d.append(-1)
				if cnode[0].left != None:
					d.append([cnode[0].left, cnode[1] - 1])
				if cnode[0].right != None:
					d.append([cnode[0].right, cnode[1] + 1])
			d.popleft()
			d.append(-1)
		return ans[0] if flag else -1


def findRecurse(root, target, depth, column):
	foundNode = None
	if root:
		if root.data == target:
			return root
	if root:
		foundNode = findRecurse(root.left, target, depth + 1, column - 1)
		if foundNode is None:
			foundNode = findRecurse(root.right, target, depth + 1, column + 1)
	return foundNode

def sumRecurse(root, depth, column):
	retSum = 0
	if root:
		if depth > 0 and column == 0:
			retSum += root.data
		retSum += sumRecurse(root.left, depth + 1, column - 1)
		retSum += sumRecurse(root.right, depth + 1, column + 1)
	return retSum

class Solution:

	def __init__(self):
		self.depth = 0

	def verticallyDownBST(self, root, target):
		nodeStart = findRecurse(root, target, 0, 0)
		if nodeStart is not None:
			return sumRecurse(nodeStart, 0, 0)
		else:
			return -1


class Solution:

	def __init__(self):
		self.targetNode = None
		self.nodeSum = 0

	def verticallyDownBST(self, root, target):
		result = self.findNode(root, target)
		if result == False:
			return -1
		self.downwardTraversal(self.targetNode, 0)
		return self.nodeSum - self.targetNode.data

	def downwardTraversal(self, node, w):
		if node is None:
			return
		if w == 0:
			self.nodeSum += node.data
		self.downwardTraversal(node.left, w + -1)
		self.downwardTraversal(node.right, w + 1)

	def findNode(self, node, target):
		if node is None:
			return False
		if node.data == target:
			self.targetNode = node
			return True
		elif node.data > target:
			return self.findNode(node.left, target)
		elif node.data < target:
			return self.findNode(node.right, target)


class Solution:

	def get_target_node(self, root, target):
		while not root.data == target:
			if root.data > target:
				if root.left is None:
					return -1
				root = root.left
			else:
				if root.right is None:
					return -1
				root = root.right
		return root

	def get_vertical_sum(self, root, sum, displacement):
		if displacement == 0:
			sum += root.data
		if root.left is not None:
			sum += self.get_vertical_sum(root.left, 0, displacement - 1)
		if root.right is not None:
			sum += self.get_vertical_sum(root.right, 0, displacement + 1)
		return sum

	def verticallyDownBST(self, root, target):
		target_node = self.get_target_node(root, target)
		if target_node == -1:
			return -1
		return self.get_vertical_sum(target_node, -target, 0)


class Solution:

	def verticallyDownBST(self, root, target):
		stack = [root]
		ans = None
		while stack:
			root_val = stack.pop()
			if root_val is None:
				continue
			if root_val.data == target:
				ans = root_val
				break
			stack.append(root_val.left)
			stack.append(root_val.right)
		if ans == None:
			return -1

		def findans(root, target):
			stack = [(root, 0)]
			dic = {}
			our_pos = 0
			while stack:
				(root_val, pos) = stack.pop()
				if root_val is None:
					continue
				if root_val.data == target:
					our_pos = pos
				if pos not in dic:
					dic[pos] = [root_val.data]
				else:
					dic[pos].append(root_val.data)
				stack.append((root_val.left, pos - 1))
				stack.append((root_val.right, pos + 1))
			ans = 0
			add = False
			for i in dic[our_pos]:
				if add:
					ans += i
				if i == target:
					add = True
			return ans
		return findans(ans, target)


class Solution:

	def verticallyDownBST(self, root, target):
		searchNode = self.findNode(root, target)
		if searchNode == None:
			return -1
		add = [0]
		self.verticalSum(searchNode, searchNode, 0, add)
		return add[0]

	def findNode(self, root, target):
		if root != None:
			if root.data == target:
				return root
			(left, right) = (None, None)
			left = self.findNode(root.left, target)
			if left != None:
				return left
			right = self.findNode(root.right, target)
			if right != None:
				return right
		return None

	def verticalSum(self, target, node, direction, add):
		if node != None:
			self.verticalSum(target, node.left, direction - 1, add)
			self.verticalSum(target, node.right, direction + 1, add)
			if target != node and direction == 0:
				add[0] += node.data


class Solution:

	def getsum(self, root, pos):
		if root is None:
			return 0
		return self.getsum(root.left, pos - 1) + self.getsum(root.right, pos + 1) + (root.data if pos == 0 else 0)

	def verticallyDownBST(self, root, target):
		if root is None:
			return -1
		if root.data == target:
			return self.getsum(root.left, -1) + self.getsum(root.right, 1)
		if root.data < target:
			return self.verticallyDownBST(root.right, target)
		return self.verticallyDownBST(root.left, target)


class Solution:

	def verticallyDownBST(self, root, target):
		dummy = None
		while root:
			if root.data == target:
				dummy = root
				break
			if root.data > target:
				root = root.left
			else:
				root = root.right
		if not dummy:
			return -1
		ans = [0]

		def fun(position, root, ref):
			if not root:
				return
			fun(position - 1, root.left, ref)
			fun(position + 1, root.right, ref)
			if position == 0 and root != ref:
				ans[0] += root.data
		fun(0, dummy, dummy)
		return ans[0]


class Solution:

	def verticallyDownBST(self, root, target):

		def find(root):
			if root == None:
				return None
			if root.data == target:
				return root
			elif root.data > target:
				return find(root.left)
			else:
				return find(root.right)
		loc = find(root)
		if loc == None:
			return -1
		q = [[loc, 0]]
		s = 0
		while q:
			for i in range(len(q)):
				ans = q.pop(0)
				node = ans[0]
				if ans[1] == 0:
					s += ans[0].data
				if node.left:
					q.append([node.left, ans[1] - 1])
				if node.right:
					q.append([node.right, ans[1] + 1])
		return s - target


class Solution:

	def __init__(self):
		self.levelFind = None
		self.colFind = None
		self.find = False
		self.summ = 0
		self.startNode = None

	def traverse(self, node, target, level, col):
		if not node:
			return -1
		if node.data < target:
			self.traverse(node.right, target, level + 1, col + 1)
		elif node.data > target:
			self.traverse(node.left, target, level + 1, col - 1)
		else:
			self.levelFind = level
			self.colFind = col
			self.find = True
			self.startNode = node

	def traverseAfter(self, node, level, col):
		if not node:
			return
		if level > self.levelFind and col == self.colFind:
			self.summ += node.data
		self.traverseAfter(node.left, level + 1, col - 1)
		self.traverseAfter(node.right, level + 1, col + 1)

	def verticallyDownBST(self, root, target):
		if not root:
			return -1
		self.traverse(root, target, 0, 0)
		if self.find:
			self.traverseAfter(self.startNode, self.levelFind, self.colFind)
			return self.summ
		return -1


class Solution:

	def verticallyDownBST(self, root, target):
		rt = root
		while True:
			if rt.data == target:
				break
			elif rt.data > target:
				if rt.left:
					rt = rt.left
				else:
					return -1
			elif rt.right:
				rt = rt.right
			else:
				return -1
		d = {}
		d[rt.data] = 0

		def inorder(root):
			if root.left:
				d[root.left.data] = d[root.data] - 1
				inorder(root.left)
			if root.right:
				d[root.right.data] = d[root.data] + 1
				inorder(root.right)
		inorder(rt)
		d1 = {}
		for i in d:
			if d[i] in d1:
				d1[d[i]].append(i)
			else:
				d1[d[i]] = [i]
		return sum(d1[0]) - target


class Solution:

	def verticallyDownBST(self, root, target):
		sol = False
		res = 0
		targetCol = 0

		def dfs(node, solved, col):
			nonlocal sol, targetCol, res
			if not node:
				return
			if solved and targetCol == col:
				res += node.data
			if node.data == target:
				targetCol = col
				sol = True
				dfs(node.left, True, col - 1)
				dfs(node.right, True, col + 1)
			else:
				dfs(node.left, solved, col - 1)
				dfs(node.right, solved, col + 1)
		dfs(root, False, 0)
		return res if sol else -1


def find(root, target):
	if root == None:
		return -1
	if root.data == target:
		return root
	if root.data > target:
		return find(root.left, target)
	return find(root.right, target)

class Solution:

	def verticallyDownBST(self, root, target):
		node = find(root, target)
		if node == -1:
			return -1
		queue = []
		su = 0
		queue.append([node, 0])
		while len(queue):
			k = queue.pop(0)
			if k[1] == 0:
				su += k[0].data
			if k[0].left != None:
				queue.append([k[0].left, k[1] - 1])
			if k[0].right != None:
				queue.append([k[0].right, k[1] + 1])
		return su - node.data


class Solution:

	def verticallyDownBST(self, root, target):

		def find(root, target):
			if root == None:
				return False
			if root.data > target:
				return find(root.left, target)
			elif root.data < target:
				return find(root.right, target)
			else:
				self.req = root
				return True
		present = find(root, target)
		if present == False:
			return -1

		def solve(root, d):
			if root == None:
				return
			if d == 0:
				self.ans += root.data
			solve(root.left, d - 1)
			solve(root.right, d + 1)
		self.ans = 0
		solve(self.req, 0)
		return self.ans - self.req.data


class Solution:

	def verticallyDownBST(self, root, target):

		def sum_below(node, level):
			while node and node.data != target:
				if node.data < target:
					node = node.right
					level += 1
				else:
					node = node.left
					level -= 1
			if not node:
				return -1
			(q, s) = ([], 0)
			if node.left:
				q.append((node.left, level - 1))
			if node.right:
				q.append((node.right, level + 1))
			while q:
				nq = []
				for (n, l) in q:
					if l == level:
						s += n.data
					if n.left:
						nq.append((n.left, l - 1))
					if n.right:
						nq.append((n.right, l + 1))
				q = nq
			return s
		return sum_below(root, 0)


class Solution:

	def verticallyDownBST(self, root, target):
		if not root:
			return

		def t_node(root, target):
			if not root:
				return
			if target < root.data:
				return t_node(root.left, target)
			elif target > root.data:
				return t_node(root.right, target)
			else:
				return root
		target_node = t_node(root, target)
		if not target_node:
			return -1
		custom_queue = [(target_node, 0, 0)]
		res = 0
		while custom_queue:
			(parent, index, level) = custom_queue[0]
			custom_queue = custom_queue[1:]
			if index == 0 and level != 0:
				res += parent.data
			if parent.left:
				custom_queue.append((parent.left, index - 1, level + 1))
			if parent.right:
				custom_queue.append((parent.right, index + 1, level + 1))
		return res


class Solution:

	def verticallyDownBST(self, root, target):

		def find(root, c, p, s):
			if root != None:
				if p == c:
					s += root.data
				s = find(root.left, c, p - 1, s)
				s = find(root.right, c, p + 1, s)
			return s

		def trav(root, target, c):
			if root != None:
				if target == root.data:
					return (root, c)
				elif target < root.data:
					return trav(root.left, target, c - 1)
				else:
					return trav(root.right, target, c + 1)
			return (None, -1)
		(root1, c) = trav(root, target, 0)
		if root1 == None:
			return c
		return find(root1, c, c, -root1.data)


MAIN = {0: 0}

class Solution:

	def verticallyDownBST(self, root, target):
		hs = 0
		while root != None:
			if root.data == target:
				self.get_sum(root, hs, 'o')
				res = MAIN[0]
				MAIN[0] = 0
				if res:
					return res
				return 0
			elif target < root.data:
				root = root.left
			else:
				root = root.right
		return -1

	def get_sum(self, root, hs, abcd):
		if root != None:
			l = self.get_sum(root.left, hs - 1, 'a')
			if not hs and abcd != 'o':
				MAIN.update({hs: MAIN[hs] + root.data if MAIN[hs] else root.data})
			r = self.get_sum(root.right, hs + 1, 'a')


class Solution:

	def verticallyDownBST(self, root, target):
		if not root:
			return

		def t_node(root, target):
			if not root:
				return
			if target < root.data:
				return t_node(root.left, target)
			elif target > root.data:
				return t_node(root.right, target)
			else:
				return root
		target_node = t_node(root, target)
		if not target_node:
			return -1
		custom_queue = [(target_node, 0, 0)]
		res = 0
		idx = 0
		flag = False
		(v_idx, lvl) = (0, 0)
		while custom_queue:
			(parent, index, level) = custom_queue[0]
			custom_queue = custom_queue[1:]
			if parent.data == target:
				(flag, v_idx, lvl) = (True, index, level)
			if flag:
				if index == v_idx and lvl != level:
					res += parent.data
			if parent.left:
				custom_queue.append((parent.left, index - 1, level + 1))
			if parent.right:
				custom_queue.append((parent.right, index + 1, level + 1))
		return res


def verticalSumUtil(root, hd, Map):
	if root == None:
		return
	verticalSumUtil(root.left, hd - 1, Map)
	if hd in Map.keys():
		Map[hd] = Map[hd] + root.data
	else:
		Map[hd] = root.data
	verticalSumUtil(root.right, hd + 1, Map)

class Solution:

	def calculate(self, root):
		Map = {}
		verticalSumUtil(root, 0, Map)
		return Map[0]

	def findNode(self, root, target):
		if root.data == target:
			return root
		elif root.left and target < root.data:
			return self.findNode(root.left, target)
		elif root.right and target > root.data:
			return self.findNode(root.right, target)

	def verticallyDownBST(self, root, target):
		nd = self.findNode(root, target)
		if not nd:
			return -1
		summation = self.calculate(nd) - nd.data
		return summation


class Solution:

	def findTarget(self, root, target):
		if root is None:
			return None
		if root.data == target:
			return root
		if root.data > target:
			return self.findTarget(root.left, target)
		return self.findTarget(root.right, target)

	def traverseVertically(self, root, position):
		if root is None:
			return 0
		left = self.traverseVertically(root.left, position + 1)
		right = self.traverseVertically(root.right, position - 1)
		if position == 0:
			result = root.data
		else:
			result = 0
		return result + left + right

	def verticallyDownBST(self, root, target):
		result = self.findTarget(root, target)
		if result is None:
			return -1
		return self.traverseVertically(result, 0) - result.data


class Solution:

	def verticallyDownBST(self, root, target):
		ans = [-1, -1]
		su = [0]

		def bfs(node, l=0, h=0):
			if node == None:
				return
			if ans[0] == l and ans[1] < h:
				su[0] += node.data
			bfs(node.left, l - 1, h + 1)
			bfs(node.right, l + 1, h + 1)
			return

		def bfs1(node, l=0, h=0):
			if node == None:
				return
			if node.data == target:
				ans[0] = l
				ans[1] = h
				bfs(node.left, l - 1, h + 1)
				bfs(node.right, l + 1, h + 1)
				return
			else:
				bfs1(node.left, l - 1, h + 1)
				bfs1(node.right, l + 1, h + 1)
			return
		bfs1(root)
		if ans[1] != -1:
			return su[0]
		return -1


class Solution:

	def verticallyDownBST(self, root, target):
		target_node = self.find_target(root, target)
		if target_node is None:
			return -1
		return self.vertical_sum(target_node, 0) - target_node.data

	def vertical_sum(self, node, column):
		_sum = 0
		if node is not None:
			if column == 0:
				_sum += node.data
			_sum += self.vertical_sum(node.left, column - 1)
			_sum += self.vertical_sum(node.right, column + 1)
		return _sum

	def find_target(self, node, target):
		if node is not None:
			if node.data == target:
				return node
			if node.data > target:
				return self.find_target(node.left, target)
			else:
				return self.find_target(node.right, target)


class Solution:

	def verticallyDownBST(self, root, target):
		queue = [root]
		v = False
		l = {}
		k = 0
		while len(queue) != 0:
			x = queue.pop(0)
			if x == None:
				continue
			elif x.data == target:
				queue = []
				l[x] = 0
				v = True
			if v == True:
				if x.left:
					l[x.left] = l[x] - 1
				if x.right:
					l[x.right] = l[x] + 1
				if x.data == target:
					pass
				elif l[x] == 0:
					k += x.data
			queue.append(x.left)
			queue.append(x.right)
		if v == False:
			return -1
		return k


def lo1(root, target):
	if root is not None:
		lo1(root.left, target)
		if root.data == target:
			m[0] = root
			m[1] = 1
		lo1(root.right, target)

def lo2(root, p):
	if root is not None:
		lo2(root.left, p - 1)
		if p == 0:
			l.append(root.data)
		lo2(root.right, p + 1)

class Solution:

	def verticallyDownBST(self, root, target):
		global l
		global m
		l = []
		m = [0, 0]
		lo1(root, target)
		if m[1] == 0:
			return -1
		lo2(m[0], 0)
		if l:
			return sum(l) - target
		return 0


class Solution:
	ans = 0

	def rootPresent(self, root, target):
		if root == None:
			return False
		if root.data > target:
			return self.rootPresent(root.left, target)
		elif root.data < target:
			return self.rootPresent(root.right, target)
		else:
			self.targ = root
			return True

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

	def verticallyDownBST(self, root, target):
		present = self.rootPresent(root, target)
		if present == False:
			return -1
		self.solve(self.targ, 0)
		return self.ans - self.targ.data


class Solution:

	def findnode(self, root):
		if not root:
			return
		if root.data == self.target:
			return root
		return self.findnode(root.left) or self.findnode(root.right)

	def verticalsum(self, root, parity):
		if not root:
			return
		if parity == 0:
			self.sum += root.data
		self.verticalsum(root.left, parity - 1)
		self.verticalsum(root.right, parity + 1)

	def verticallyDownBST(self, root, target):
		self.target = target
		cur = self.findnode(root)
		if not cur:
			return -1
		self.sum = 0
		self.verticalsum(cur.left, -1)
		self.verticalsum(cur.right, +1)
		return self.sum


class Solution:

	def verticallyDownBST(self, root, target):
		self.foundTarget = False
		self.target = target
		self.ans = 0
		self.find(root)
		if not self.foundTarget:
			return -1
		return self.ans - target

	def verticalTraversal(self, r, val):
		if r is not None:
			if self.foundTarget and self.targetLevel == val:
				self.ans += r.data
			self.verticalTraversal(r.left, val - 1)
			self.verticalTraversal(r.right, val + 1)

	def find(self, r):
		if r is not None:
			if not self.foundTarget and r.data == self.target:
				self.foundTarget = True
				self.targetLevel = 0
				self.verticalTraversal(r, 0)
				return
			elif self.foundTarget:
				return
			self.find(r.left)
			self.find(r.right)


class Solution:

	def verticallyDownBST(self, root, target):
		level = 0
		is_present = False
		target_ind = 0
		while root:
			if root.data == target:
				is_present = True
				break
			if root.data > target:
				root = root.left
				target_ind -= 1
			else:
				root = root.right
				target_ind += 1
		if not is_present:
			return -1
		result = [0]

		def fun(root, target_ind, ind):
			if root == None:
				return
			if target_ind == ind:
				result[0] += root.data
			fun(root.left, target_ind, ind - 1)
			fun(root.right, target_ind, ind + 1)
		fun(root, target_ind, target_ind)
		return result[0] - target


class Solution:

	def verticallyDownBST(self, root, target):
		arr = [0, 0]
		node = [0]
		found = self.find(root, target, 0, 0, arr, node)
		if not found:
			return -1
		return self.getsum(node[0], target, arr[0], arr[1], arr)

	def find(self, root, target, h, v, arr, node):
		if root == None:
			return False
		if root.data == target:
			arr[0] = h
			arr[1] = v
			node[0] = root
			return True
		if root.left:
			ans = self.find(root.left, target, h + 1, v - 1, arr, node)
			if ans:
				return True
		if root.right:
			ans = self.find(root.right, target, h + 1, v + 1, arr, node)
			if ans:
				return True
		return False

	def getsum(self, root, target, h, v, arr):
		if root == None:
			return 0
		if h > arr[0] and v == arr[1]:
			return root.data + self.getsum(root.left, target, h + 1, v - 1, arr) + self.getsum(root.right, target, h + 1, v + 1, arr)
		return self.getsum(root.left, target, h + 1, v - 1, arr) + self.getsum(root.right, target, h + 1, v + 1, arr)


class Solution:

	def find(self, root, val, f):
		if root:
			if f and val == 0:
				self.ans += root.data
			if root.data == target:
				self.f = 1
				self.find(root.left, -1, 1)
				self.find(root.right, 1, 1)
			else:
				self.find(root.left, val - 1, f)
				self.find(root.right, val + 1, f)

	def verticallyDownBST(self, root, target):
		self.ans = 0
		self.f = 0
		self.find(root, 0, 0)
		if not self.f:
			return -1
		return self.ans