You are given a Binary Search Tree and a target value. You must find the maximum difference between the sum of node data from root to target and from target to a child leaf node (target exclusive). Initially, you are at the root node.
Note: If the target node is not present in the tree then return -1.
Example 1:
Input:
Target = 20
Output: 10
Explanation: From root to target the sum of node data is 25 and from target to the children leaf nodes the sums of the node data are 15 and 22. So, the maximum difference will be (25-15) = 10.
Example 2:
Input:
Target = 50
Output: -1
Explanation: The target node is not present in the tree.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxDifferenceBST() which takes BST(you are given the root node of the BST ) and target as input, and returns an interger value as the required answer. If the target is not present in the BST then return -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(H), H - Height of the Tree.
Constraints:
1 <= n < 10^4
1 <= node.data < 10^5
1 <= target < 10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Graph traversal

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 maxDifferenceBST(self,root, target):

        #code here

Solutions:
class Solution:

	def maxDifferenceBST(self, root, target):
		(tg_node, root_sum) = self.get_target_node(root, target, 0)
		if not tg_node:
			return -1
		leaf_sum = self.tg_to_leaf_sum(tg_node, 0)
		return root_sum - (leaf_sum - tg_node.data)

	def tg_to_leaf_sum(self, tg, sum_):
		if not tg:
			return float('inf')
		if not tg.left and (not tg.right):
			return sum_ + tg.data
		return min(self.tg_to_leaf_sum(tg.left, sum_ + tg.data), self.tg_to_leaf_sum(tg.right, sum_ + tg.data))

	def get_target_node(self, node, target, sum_):
		if not node:
			return (node, -1)
		if node.data == target:
			return (node, sum_)
		if target < node.data:
			return self.get_target_node(node.left, target, sum_ + node.data)
		return self.get_target_node(node.right, target, sum_ + node.data)


class Solution:

	def maxDifferenceBST(self, root, target):
		sm = 0
		cur = root
		lr = 1
		while cur.data != target:
			sm += cur.data
			if cur.data > target:
				if cur.left:
					cur = cur.left
				else:
					return -1
			elif cur.right:
				cur = cur.right
			else:
				return -1

		def mn_mx(node, mn=0, mx=0):
			if not node.left and (not node.right):
				return (mn, mx)
			(x, y) = (float('inf'), -float('inf'))
			if node.left:
				(a, b) = mn_mx(node.left, mn + node.left.data, mx + node.left.data)
				x = min(x, min(a, b))
				y = max(y, max(a, b))
			if node.right:
				(a, b) = mn_mx(node.right, mn + node.right.data, mx + node.right.data)
				x = min(x, min(a, b))
				y = max(y, max(a, b))
			return (x, y)
		(mn, mx) = mn_mx(cur)
		return max(sm - mn, sm - mx)


class Solution:

	def maxDifferenceBST(self, root, target):

		def func(root, target, li, sumi):
			if root is None:
				return False
			if root.data == target:
				li.append([sumi, root])
				return True
			left = func(root.left, target, li, sumi + root.data)
			right = func(root.right, target, li, sumi + root.data)
			return left or right
		li = []
		func(root, target, li, 0)
		if not li:
			return -1
		total = li[0][0]
		rootdata = li[0][1]

		def func1(rootdata):
			if rootdata.left is None and rootdata.right is None:
				return rootdata.data
			if rootdata.left is None and rootdata.right:
				return rootdata.data + func1(rootdata.right)
			if rootdata.left and rootdata.right is None:
				return rootdata.data + func1(rootdata.left)
			left = func1(rootdata.left)
			right = func1(rootdata.right)
			return min(left + rootdata.data, right + rootdata.data)
		kk = func1(rootdata)
		ans = kk - target
		return total - ans


class Solution:

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

		def dfs(root, target, s):
			if root == None:
				return 0
			if root.data == target:
				l.append(root)
				l.append(s + root.data)
				return
			dfs(root.left, target, s + root.data)
			dfs(root.right, target, s + root.data)
		dfs(root, target, 0)
		if len(l) == 0:
			return -1

		def maxdiff(root, s):
			if root == None:
				return -10 ** 9
			if root.left == None and root.right == None:
				return s - root.data
			return max(maxdiff(root.left, s - root.data), maxdiff(root.right, s - root.data))
		return maxdiff(l[0], l[1])


class Solution:

	def maxDifferenceBST(self, root, target):
		if root is None:
			return -1

		def path(root):
			from collections import deque
			q = deque()
			q.append((root, [root.data]))
			ds = []
			while q:
				(s, l) = q.popleft()
				if not s.left and (not s.right):
					ds += [sum(l) - target]
				else:
					if s.left:
						q.append((s.left, l + [s.left.data]))
					if s.right:
						q.append((s.right, l + [s.right.data]))
			return ds
		from collections import deque
		q = deque()
		q.append((root, [root.data]))
		ds = []
		current = root
		while q:
			(s, l) = q.popleft()
			if s.data == target and s == current:
				k1 = path(s)
				m1 = sum(l) - current.data
				ma = -999999999
				for i in k1:
					ma = max(m1 - i, ma)
				return ma
			elif s.data == target:
				k1 = path(s)
				m1 = sum(l) - target
				ma = -999999999
				for i in k1:
					ma = max(m1 - i, ma)
				return ma
			if s.left:
				q.append((s.left, l + [s.left.data]))
			if s.right:
				q.append((s.right, l + [s.right.data]))
		return -1


class Solution:

	def maxDifferenceBST(self, root, target):
		from collections import deque

		def find(target, root, s):
			while root != None:
				s += root.data
				if root.data == target:
					s -= root.data
					return (root, s)
				if root.data < target:
					root = root.right
				else:
					root = root.left
			return (None, 0)
		(k, sums) = find(target, root, 0)
		if k == None:
			return -1
		l = []
		q = deque()
		q.append((k, 0))
		while q:
			(n, s) = q.popleft()
			if n.left == None and n.right == None:
				l.append(s)
			if n.left:
				q.append((n.left, s + n.left.data))
			if n.right:
				q.append((n.right, s + n.right.data))
		maxdif = -78367862732
		for i in l:
			maxdif = max(maxdif, sums - i)
		return maxdif


class Solution:

	def maxDifferenceBST(self, root, target):

		def minpath(root):
			if not root:
				return 0
			l = minpath(root.left)
			r = minpath(root.right)
			if l == 0:
				l = 99999999999
			if r == 0:
				r = 99999999999
			if l == 99999999999 and r == 99999999999:
				(l, r) = (0, 0)
			return root.data + min(l, r)
		x = [None]
		psum = [0]

		def find(root):
			if not root:
				return
			psum[0] += root.data
			if root.data == target:
				x[0] = root
			if root.data < target:
				find(root.right)
			if root.data > target:
				find(root.left)
		find(root)
		if x[0]:
			xsum = minpath(x[0]) - x[0].data
			psum[0] -= x[0].data
			return psum[0] - xsum
		else:
			return -1


class Solution:

	def dfs(self, node):
		if not node:
			return 0
		sl = sr = float('inf')
		if node.left:
			sl = self.dfs(node.left)
		if node.right:
			sr = self.dfs(node.right)
		sm = min(sl, sr)
		if sm == float('inf'):
			return node.data
		return sm + node.data

	def maxDifferenceBST(self, root, target):
		sm1 = 0
		cur = root
		while cur.data != target:
			flag = False
			sm1 += cur.data
			if cur.left and cur.data > target:
				cur = cur.left
				flag = True
			elif cur.right and cur.data < target:
				cur = cur.right
				flag = True
			if not flag:
				return -1
		sm2 = self.dfs(cur) - target
		return sm1 - sm2


class Solution:

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

		def find(root, target):
			if root == None:
				return None
			if root.data == target:
				return root
			l[0] += root.data
			if root.data > target:
				return find(root.left, target)
			if root.data < target:
				return find(root.right, target)
			return None

		def findMin(root):
			if root.left == None and root.right == None:
				return root.data
			if root.right == None:
				return findMin(root.left) + root.data
			if root.left == None:
				return findMin(root.right) + root.data
			return min(findMin(root.right), findMin(root.left)) + root.data
		node = find(root, target)
		if node == None:
			return -1
		return l[0] - (findMin(node) - node.data)


class Solution:

	def solve(self, root, t, sm):
		if root == None:
			return [False, sm, -1]
		if root.data == t:
			return [True, sm, root]
		l = self.solve(root.left, t, sm + root.data)
		if l[0] == True:
			return l
		r = self.solve(root.right, t, sm + root.data)
		if r[0] == True:
			return r
		return [False, sm, -1]

	def solve1(self, root, s, ans):
		if root.left == None and root.right == None:
			if s + root.data < ans:
				ans = s + root.data
			return ans
		if root.left != None:
			ans = self.solve1(root.left, s + root.data, ans)
		if root.right != None:
			ans = self.solve1(root.right, s + root.data, ans)
		return ans

	def maxDifferenceBST(self, root, target):
		cal = self.solve(root, target, 0)
		if cal[0] == False:
			return -1
		ans = pow(10, 9)
		ans = self.solve1(cal[2], 0, ans)
		return cal[1] - (ans - cal[2].data)


class Solution:

	def getsums(self, node, presum):
		if node.left is None and node.right is None:
			return [presum + node.data]
		ans = []
		if node.left is not None:
			ans += self.getsums(node.left, presum + node.data)
		if node.right is not None:
			ans += self.getsums(node.right, presum + node.data)
		return ans

	def maxDifferenceBST(self, root, target):
		cur = root
		s1 = 0
		while cur and cur.data != target:
			s1 += cur.data
			if cur.data < target:
				cur = cur.right
			else:
				cur = cur.left
		if cur is None:
			return -1
		s2 = self.getsums(cur, 0)
		return s1 + target - min(s2)


class Solution:

	def search(self, root, target, ans):
		if not root:
			return None
		if root.data == target:
			return root
		self.ans += root.data
		if target > root.data:
			return self.search(root.right, target, ans)
		else:
			return self.search(root.left, target, ans)

	def dfs(self, node):
		res = node.data
		mn = 10 ** 9
		if node.left:
			mn = min(mn, self.dfs(node.left))
		if node.right:
			mn = min(mn, self.dfs(node.right))
		if mn == 10 ** 9:
			return res
		else:
			return res + mn

	def maxDifferenceBST(self, root, target):
		self.ans = 0
		node = self.search(root, target, self.ans)
		if node == None:
			return -1
		self.ans -= self.dfs(node) - node.data
		return self.ans


class Solution:

	def maxDifferenceBST(self, root, target):

		def t_to_c(root, cur):
			nonlocal y
			if root.left == None and root.right == None:
				cur += root.data
				y = min(cur, y)
				return
			if root.left:
				t_to_c(root.left, cur + root.data)
			if root.right:
				t_to_c(root.right, cur + root.data)

		def root_to_t(root, target):
			nonlocal x
			if root == None:
				return root
			if root.data == target:
				return root
			x += root.data
			if root.data < target:
				return root_to_t(root.right, target)
			else:
				return root_to_t(root.left, target)
		(x, y) = (0, float('inf'))
		tmp = root_to_t(root, target)
		if tmp == None:
			return -1
		t_to_c(tmp, 0)
		y -= target
		return x - y


class Solution:
	ans = 0
	sum1 = 0

	def maxDifferenceBST(self, root, target):
		temp = root
		Solution.sum1 = 0
		while temp:
			if temp.data == target:
				break
			if target < temp.data:
				Solution.sum1 += temp.data
				temp = temp.left
			else:
				Solution.sum1 += temp.data
				temp = temp.right
		if not temp:
			return -1
		Solution.ans = float('-inf')
		if not temp.left and (not temp.right):
			return Solution.sum1
		if temp.left:
			Solution.fun(temp.left, 0)
		if temp.right:
			Solution.fun(temp.right, 0)
		return Solution.ans

	@staticmethod
	def fun(curr, sum2):
		if not curr:
			return
		if not curr.left and (not curr.right):
			sum2 += curr.data
			Solution.ans = max(Solution.ans, Solution.sum1 - sum2)
			return
		Solution.fun(curr.left, sum2 + curr.data)
		Solution.fun(curr.right, sum2 + curr.data)


class Solution:

	def maxDifferenceBST(self, root, target):

		def mxsm(root):
			if not root:
				return -1
			if root.data == target:
				mxsm.targetRef = root
				return 0
			if target < root.data:
				temp = mxsm(root.left)
			else:
				temp = mxsm(root.right)
			return temp + root.data if temp != -1 else -1

		def mnsm(root):
			if not root:
				return float('inf')
			if not root.left and (not root.right):
				return root.data
			left = mnsm(root.left)
			right = mnsm(root.right)
			mn = min(left, right)
			return mn + root.data
		_a = mxsm(root)
		if _a == -1:
			return -1
		_b = mnsm(mxsm.targetRef) - mxsm.targetRef.data
		return _a - _b


class Solution:

	def maxDifferenceBST(self, root, target):

		def result(root):
			if root == None:
				return 1000000000.0
			if root.left == None and root.right == None:
				return root.data
			l = result(root.left)
			r = result(root.right)
			return min(l, r) + root.data
		val = [0]

		def solve(root, t):
			if root == None:
				return -1
			if root.data == t:
				val[0] = min(result(root.left), result(root.right))
				return 0
			if root.data > t:
				ans = solve(root.left, t)
			else:
				ans = solve(root.right, t)
			if ans != -1:
				return ans + root.data
			else:
				return -1
		res = solve(root, target)
		if val[0] == 1000000000.0:
			return res
		return res - val[0]


class Solution:

	def maxDifferenceBST(self, root, target):
		x = []
		z = []

		def helper(root, t):
			if not root:
				return False
			if root.data == t:
				z.append(root)
				x.append(root.data)
				return True
			l = helper(root.left, t)
			r = helper(root.right, t)
			if l or r:
				x.append(root.data)
				return True
			return False
		helper(root, target)
		if not x:
			return -1

		def helper2(root):
			if not root:
				return 999999999
			if root.left == None and root.right == None:
				return root.data
			l = helper2(root.left)
			r = helper2(root.right)
			return root.data + min(l, r)
		a = helper2(z[0])
		return sum(x) - a


class Solution:

	def __init__(self):
		self.sum_list = []
		self.sum_root_to_target = 0
		self.sum_target_to_leaf = 0
		self.target_node = None

	def maxDifferenceBST(self, root, target):
		self.root_to_targeT_sum(root, target)
		if self.sum_root_to_target == -1:
			return -1
		self.target_to_leaf_sum(self.target_node)
		max_value = max(list((self.sum_root_to_target - i for i in self.sum_list)))
		return max_value

	def root_to_targeT_sum(self, root, target):
		i_node = root
		if i_node is None:
			self.sum_root_to_target = -1
		elif target == i_node.data:
			self.target_node = i_node
		elif target < i_node.data:
			self.sum_root_to_target += i_node.data
			self.root_to_targeT_sum(i_node.left, target)
		else:
			self.sum_root_to_target += i_node.data
			self.root_to_targeT_sum(i_node.right, target)

	def target_to_leaf_sum(self, target, value=0):
		if target.left is not None or target.right is not None:
			sum_lef = 0
			sum_rig = 0
			if target.left is not None:
				sum_lef = self.target_to_leaf_sum(target.left, value=target.left.data + value)
			if target.right is not None:
				sum_rig = self.target_to_leaf_sum(target.right, value=target.right.data + value)
		else:
			self.sum_list.append(value)
			return


import sys

class Solution:

	def path(self, root, target, sum1, lst):
		if root is None:
			return None
		sum1 += root.data
		lst.append(sum1)
		if root.data == target:
			return root
		if target > root.data:
			return self.path(root.right, target, sum1, lst)
		else:
			return self.path(root.left, target, sum1, lst)

	def leafNode(self, newRoot):
		if newRoot.left == None and newRoot.right == None:
			return newRoot.data
		a = sys.maxsize
		if newRoot.left:
			a = min(a, self.leafNode(newRoot.left))
		if newRoot.right:
			a = min(a, self.leafNode(newRoot.right))
		return a + newRoot.data

	def maxDifferenceBST(self, root, target):
		x = 0
		lst = []
		targetNode = self.path(root, target, x, lst)
		x = lst[-1]
		if targetNode == None:
			return -1
		sum2 = self.leafNode(targetNode)
		ans = x - sum2
		return ans


class Solution:

	def maxDifferenceBST(self, root, target):

		def min_val(node):
			if not node.left and (not node.right):
				return node.data
			cur = 10000000.0
			if node.left:
				cur = min(cur, min_val(node.left))
			if node.right:
				cur = min(cur, min_val(node.right))
			return node.data + cur
		s = 0
		ptr = root
		while True:
			if not ptr:
				return -1
			if target == ptr.data:
				break
			elif target < ptr.data:
				s += ptr.data
				ptr = ptr.left
			else:
				s += ptr.data
				ptr = ptr.right
		diff = min_val(ptr)
		return s - diff + target


class Solution:

	def maxDifferenceBST(self, root, target):

		def fun2(root):
			if root.left and root.right:
				(leftmin, leftmax) = fun2(root.left)
				(rightmin, rightmax) = fun2(root.right)
				return (min([leftmin, leftmax, rightmin, rightmax]) + root.data, max([leftmin, leftmax, rightmin, rightmax]) + root.data)
			elif root.left:
				(leftmin, leftmax) = fun2(root.left)
				return (root.data + leftmin, root.data + leftmax)
			elif root.right:
				(rightmin, rightmax) = fun2(root.right)
				return (root.data + rightmin, root.data + rightmax)
			else:
				return (root.data, root.data)

		def fun(root, target, s):
			if not root:
				return -1
			if root.data == target:
				if root.left and root.right:
					(downmin, downmax) = fun2(root)
					downmin -= root.data
					downmax -= root.data
					return max(s - downmin, s - downmax)
				if root.left:
					(downmin, downmax) = fun2(root.left)
					return max(s - downmin, s - downmax)
				if root.right:
					(downmin, downmax) = fun2(root.right)
					return max(s - downmin, s - downmax)
				else:
					return s
			if target < root.data:
				return fun(root.left, target, s + root.data)
			else:
				return fun(root.right, target, s + root.data)
		return fun(root, target, 0)


class Solution:

	def maxDifferenceBST(self, root, target):
		global targetNode
		targetNode = None
		sum1 = self.getRootToTargetSum(root, target)
		if not targetNode:
			return -1
		sum2 = self.targetToRoot(targetNode)
		return sum1 - sum2

	def getRootToTargetSum(self, root, target):
		if not root:
			return -10 ** 5
		if target == root.data:
			global targetNode
			targetNode = root
			return target
		if target < root.data:
			return root.data + self.getRootToTargetSum(root.left, target)
		else:
			return root.data + self.getRootToTargetSum(root.right, target)

	def targetToRoot(self, target):
		if not target:
			return 10 ** 5
		if not target.left and (not target.right):
			return target.data
		left = target.data + self.targetToRoot(target.left)
		right = target.data + self.targetToRoot(target.right)
		return min(left, right)


class Solution:

	def __init__(self):
		self.targetSum = 0
		self.childSum = float('inf')
		self.targetNode = None

	def findTarget(self, node, target):
		while node:
			self.targetSum += node.data
			if target < node.data:
				node = node.left
			else:
				node = node.right
			if node and node.data == target:
				self.targetNode = node
				break

	def leafTraversal(self, node, curr_sum):
		if not node:
			return curr_sum
		self.leafTraversal(node.left, curr_sum + node.data)
		self.leafTraversal(node.right, curr_sum + node.data)
		if not node.left and (not node.right):
			self.childSum = min(self.childSum, curr_sum + node.data)

	def maxDifferenceBST(self, root, target):
		if not root:
			return -1
		if target == root.data:
			self.targetNode = root
		else:
			self.findTarget(root, target)
		if self.targetNode == None:
			return -1
		self.leafTraversal(self.targetNode.left, 0)
		self.leafTraversal(self.targetNode.right, 0)
		if not self.targetNode.left and (not self.targetNode.right):
			self.childSum = 0
		return self.targetSum - self.childSum


class Solution:

	def maxDifferenceBST(self, root, target):
		sum1 = [0] * 1
		node = [0] * 1

		def fun(root):
			if root == None:
				return
			if root.data == target:
				node[0] = root
				return
			sum1[0] += root.data
			if root.data > target:
				fun(root.left)
			else:
				fun(root.right)
		fun(root)
		if node[0] == 0:
			return -1
		sum2 = [10 ** 10]

		def fun1(root, s):
			if root == None:
				return
			if root.left == None and root.right == None:
				sum2[0] = min(sum2[0], s + root.data)
			fun1(root.left, s + root.data)
			fun1(root.right, s + root.data)
		fun1(node[0], -node[0].data)
		return sum1[0] - sum2[0]


class Solution:

	def maxDifferenceBST(self, root, target):
		temp = root
		sum = 0

		def solve(root):
			if root == None:
				return 1000000000.0
			if root.left == None and root.right == None:
				return root.data
			(left, right) = (solve(root.left), solve(root.right))
			return root.data + min(left, right)
		while temp:
			if temp.data == target:
				mn = solve(temp)
				return sum - mn + target
			elif temp.data < target:
				sum += temp.data
				temp = temp.right
			else:
				sum += temp.data
				temp = temp.left
		return -1


class Solution:

	def maxDifferenceBST(self, root, target):
		(target_node, root_sum) = self.find_target_node(root, target, 0)
		if not target_node:
			return -1
		leaf_sum = self.target_to_leaf_sum(target_node, 0)
		return root_sum - (leaf_sum - target_node.data)

	def target_to_leaf_sum(self, target, sum_):
		if not target:
			return float('inf')
		if not target.left and (not target.right):
			return sum_ + target.data
		return min(self.target_to_leaf_sum(target.left, sum_ + target.data), self.target_to_leaf_sum(target.right, sum_ + target.data))

	def find_target_node(self, node, target, sum_):
		if not node:
			return (node, -1)
		if node.data == target:
			return (node, sum_)
		if target < node.data:
			return self.find_target_node(node.left, target, sum_ + node.data)
		return self.find_target_node(node.right, target, sum_ + node.data)


class Solution:

	def maxDifferenceBST(self, root, target):
		p = root
		a = 0
		while p.data != target:
			a += p.data
			if p.data > target and p.left != None:
				p = p.left
			elif p.data < target and p.right != None:
				p = p.right
			else:
				break
		if p.data != target:
			return -1
		b = 0
		c = 1000000000.0
		d = [[p.left, 0], [p.right, 0]]
		while len(d) > 0:
			r = d.pop()
			if r[0] != None:
				r[1] += r[0].data
				if r[0].left == None and r[0].right == None:
					b = max(b, r[1])
					c = min(c, r[1])
				d.append([r[0].left, r[1]])
				d.append([r[0].right, r[1]])
		if a - c > a - b:
			return a - c
		else:
			return a - b


class Solution:

	def maxDifferenceBST(self, root, target):
		s = 0

		def find(n):
			nonlocal s
			if not n:
				return None
			if n.data == target:
				return n
			s += n.data
			if n.data > target:
				return find(n.left)
			return find(n.right)
		tn = find(root)
		if not tn:
			return -1
		ans = float('-inf')

		def dfs(n, sv=0):
			nonlocal ans, s
			if not n:
				return
			sv += n.data
			if not n.left and (not n.right):
				ans = max(ans, s - sv)
			else:
				dfs(n.left, sv)
				dfs(n.right, sv)
		dfs(tn.left)
		dfs(tn.right)
		return s if ans == float('-inf') else ans


class Solution:

	def maxDifferenceBST(self, root, target):

		def find(root, target, ans):
			if root == None:
				return (-1, 0)
			if root.data == target:
				return (ans, root)
			if root.data < target:
				ans += root.data
				return find(root.right, target, ans)
			else:
				ans += root.data
				return find(root.left, target, ans)
		ans = 0
		(ts, root) = find(root, target, ans)
		if ts == -1:
			return -1

		def finms(root, ans1):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return root.data
			if root.left == None:
				return root.data + finms(root.right, ans)
			if root.right == None:
				return root.data + finms(root.left, ans)
			else:
				return root.data + min(finms(root.left, ans), finms(root.right, ans))
		ans1 = float('inf')
		tms = finms(root, ans1)
		return ts - (tms - root.data)


class Solution:

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

	def top(self, root, nodeval):
		if root == None:
			return 0
		if root.data == nodeval:
			return root.data
		if root.data > nodeval:
			return root.data + self.top(root.left, nodeval)
		else:
			return root.data + self.top(root.right, nodeval)

	def bot(self, node):
		if node == None:
			return 0
		if node.left == None and node.right == None:
			return node.data
		if node.left == None:
			return node.data + self.bot(node.right)
		if node.right == None:
			return node.data + self.bot(node.left)
		return min(node.data + self.bot(node.left), node.data + self.bot(node.right))

	def maxDifferenceBST(self, root, target):
		node = self.find(root, target)
		if node == None:
			return -1
		else:
			sum1 = self.top(root, node.data) - node.data
			sum2 = self.bot(node) - node.data
			return sum1 - sum2


class Solution:

	def solve(self, root, sumval):
		if root is None:
			return
		if root.left is None and root.right is None:
			self.res = max(self.res, self.lsum - (sumval + root.data))
			return
		sumval = sumval + root.data
		self.solve(root.left, sumval)
		self.solve(root.right, sumval)

	def findlsum(self, root, target):
		if root is None:
			return
		if root.data == target:
			return root
		self.lsum = self.lsum + root.data
		if root.data < target:
			return self.findlsum(root.right, target)
		else:
			return self.findlsum(root.left, target)

	def maxDifferenceBST(self, root, target):
		self.lsum = 0
		self.res = -10 ** 5
		troot = self.findlsum(root, target)
		if troot is None:
			return -1
		if troot.left is not None:
			self.solve(troot.left, 0)
		if troot.right is not None:
			self.solve(troot.right, 0)
		if self.res == -10 ** 5:
			return self.lsum
		return self.res


class Solution:

	def maxDifferenceBST(self, root, target):

		def solve(node):
			if not node:
				return 0
			if node.left and node.right:
				return node.data + min(solve(node.left), solve(node.right))
			else:
				return node.data + solve(node.left) + solve(node.right)
		rtot = 0
		temp = root
		while temp:
			if temp.data == target:
				ttol = solve(temp) - target
				return rtot - ttol
			elif temp.data < target:
				rtot += temp.data
				temp = temp.right
			else:
				rtot += temp.data
				temp = temp.left
		return -1


class Solution:

	def maxDifferenceBST(self, root, target):
		val = 0
		queue = [(root, val)]

		def solve(r):
			if r.left == None and r.right == None:
				return r.data
			if r.right and r.left:
				return r.data + min(solve(r.right), solve(r.left))
			if r.right:
				return r.data + solve(r.right)
			if r.left:
				return r.data + solve(r.left)
		while queue:
			x = queue.pop(0)
			node = x[0]
			val = x[1]
			if node.data == target:
				ans = solve(node) - node.data
				return val - ans
			if node.left:
				queue.append((node.left, val + node.data))
			if node.right:
				queue.append((node.right, val + node.data))
		return -1


class Solution:
	ans = -2147483648

	def maxDifferenceBST(self, root, target):
		res = 0
		while root != None:
			if root.data == target:
				break
			elif root.data < target:
				res += root.data
				root = root.right
			else:
				res += root.data
				root = root.left
		if root == None:
			return -1
		Solution.ans = -2147483648
		if root.left == None and root.right == None:
			return res
		if root.left != None:
			self.solve(root.left, 0, res)
		if root.right != None:
			self.solve(root.right, 0, res)
		return Solution.ans

	def solve(self, root, path_sum, res):
		if root == None:
			return
		if root.left == None and root.right == None:
			Solution.ans = max(Solution.ans, res - (path_sum + root.data))
			return
		self.solve(root.left, path_sum + root.data, res)
		self.solve(root.right, path_sum + root.data, res)


class Solution:

	def maxDifferenceBST(self, root, target):

		def dfs(node):
			res = node.data
			minimum = float('inf')
			if node.left:
				minimum = min(minimum, dfs(node.left))
			if node.right:
				minimum = min(minimum, dfs(node.right))
			if minimum == float('inf'):
				return res
			else:
				return minimum + res
		sum_target = 0
		while root and root.data != target:
			if root.data > target:
				sum_target += root.data
				root = root.left
			elif root.data < target:
				sum_target += root.data
				root = root.right
		if not root:
			return -1
		return sum_target - dfs(root) + root.data


class Solution:

	def rootToTarg(self, root, target, sum1, targ):
		if not root:
			return
		if root.data == target:
			targ[0] = root
			return
		sum1[0] += root.data
		if root.data > target:
			self.rootToTarg(root.left, target, sum1, targ)
		else:
			self.rootToTarg(root.right, target, sum1, targ)

	def dfs(self, targ):
		if not targ:
			return float('inf')
		if not targ.left and (not targ.right):
			return targ.data
		(left, right) = (float('inf'), float('inf'))
		if targ.left:
			left = self.dfs(targ.left)
		if targ.right:
			right = self.dfs(targ.right)
		return targ.data + min(left, right)

	def maxDifferenceBST(self, root, target):
		if not root:
			return -1
		sum1 = [0]
		targ = [None]
		self.rootToTarg(root, target, sum1, targ)
		if not targ[0]:
			return -1
		if not targ[0].left and (not targ[0].right):
			return sum1[0]
		return sum1[0] - min(self.dfs(targ[0].left), self.dfs(targ[0].right))


class Solution:

	def maxDifferenceBST(self, root, target):

		def fun1(root):
			if root is None:
				return 1000000000.0
			if root.left is None and root.right is None:
				return root.data
			l = fun1(root.left)
			r = fun1(root.right)
			return min(l, r) + root.data
		ans = [0]

		def fun(root, t):
			if root is None:
				return -1
			if root.data == t:
				ans[0] = min(fun1(root.left), fun1(root.right))
				return 0
			if root.data > t:
				h = fun(root.left, t)
			else:
				h = fun(root.right, t)
			if h != -1:
				return h + root.data
			else:
				return -1
		res = fun(root, target)
		if ans[0] == 1000000000.0:
			return res
		return res - ans[0]


class Solution:

	def __init__(self):
		self.target_node = None

	def maxDifferenceBST(self, root, target):
		root_target_sum = self.findTargetNodeSum(root, target)
		if self.target_node == None:
			return -1
		min_leaf_sum = self.findMinPathToLeaf(self.target_node) - target
		return root_target_sum - min_leaf_sum

	def findTargetNodeSum(self, node, target):
		if node == None:
			return 0
		curr_val = node.data
		if curr_val == target:
			self.target_node = node
			return 0
		elif target < curr_val:
			return curr_val + self.findTargetNodeSum(node.left, target)
		else:
			return curr_val + self.findTargetNodeSum(node.right, target)

	def findMinPathToLeaf(self, node):
		if node == None:
			return float('inf')
		if node.left == None and node.right == None:
			return node.data
		return node.data + min(self.findMinPathToLeaf(node.left), self.findMinPathToLeaf(node.right))


class Solution:

	def maxDifferenceBST(self, root, target):
		try:

			def dfs(root):
				if not root:
					return (float('inf'), float('-inf'), False)
				if root.left is None and root.right is None:
					if root.data == target:
						return (0, 0, True)
					return (root.data, root.data, False)
				(min1, max1, found1) = dfs(root.left)
				(min2, max2, found2) = dfs(root.right)
				if found1:
					return (min1 + root.data, max1, True)
				if found2:
					return (min2 + root.data, max2, True)
				if root.data == target:
					if min1 == float('inf') and min2 == float('inf'):
						return (0, 0, True)
					if min1 == float('inf'):
						return (0, min2, True)
					if min2 == float('inf'):
						return (0, min1, True)
					return (0, min(min1, min2), True)
				return (min(min1, min2) + root.data, max(max1, max2) + root.data, False)
			(s1, s2, found) = dfs(root)
			if not found:
				return -1
			return s1 - s2
		except Exception as e:
			print(e)
			return 0


class Solution:

	def maxDifferenceBST(self, root, target):

		def tillTarget(root):
			nonlocal next_root
			if root:
				if root.data == target:
					next_root = root
					return root.data
				if target > root.data:
					return root.data + tillTarget(root.right)
				else:
					return root.data + tillTarget(root.left)
			else:
				return float('-inf')

		def toLeaf(root):
			if root == None:
				return float('inf')
			if root.left == root.right == None:
				return root.data
			return root.data + min(toLeaf(root.left), toLeaf(root.right))
		next_root = None
		sol = tillTarget(root)
		if next_root == None:
			return -1
		return sol - toLeaf(next_root)