Given a binary tree and a target, find the number of node in the minimum sub-tree with the given sum equal to the target which is also a binary search tree.
Example 1:
Input:
           13
         /    \
       5       23
      / \      / \
     N   17   N   N
         /
        16
Target: 38
Output: 3
Explanation: 5,17,16 is the smallest subtree
with length 3.
 
Example 2:
Input:
             7
           /   \
          N    23
             /   \
            10    23
           /  \   / \
          N   17 N   N
Target: 73
Output: -1
Explanation: No subtree is bst for the given target.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minSubtreeSumBST() which takes the tree root and target as input parameters which is a binary Tree and returns the length of the minimum subtree having a sum equal to the target but which is a binary search tree.
Expected Time Complexity: O(N), where N is no. of nodes
Expected Space Complexity: O(h), where h is the height of the tree
Constraints:
1 <= N <= 10^5

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

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

        #code here

Solutions:
class Solution:

	def minSubtreeSumBST(self, target, root):
		res = float(inf)

		def traverse(node):
			nonlocal res
			if not node:
				return (float(inf), float(-inf), 0, 0)
			left = traverse(node.left)
			right = traverse(node.right)
			if not left or not right:
				return
			(leftMin, leftMax, leftSum, leftSumNode) = (left[0], left[1], left[2], left[3])
			(rightMin, rightMax, rightSum, rightSumNode) = (right[0], right[1], right[2], right[3])
			if node.data > leftMax and node.data < rightMin:
				nodeMax = max(rightMax, node.data)
				nodeMin = min(leftMin, node.data)
				nodeSum = leftSum + rightSum + node.data
				if nodeSum == target:
					res = min(res, leftSumNode + rightSumNode + 1)
				return (nodeMin, nodeMax, nodeSum, leftSumNode + rightSumNode + 1)
		traverse(root)
		return res if res != float(inf) else -1


def su(root):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		return root.data
	l = su(root.left)
	r = su(root.right)
	return root.data + l + r

def size(root):
	if root == None:
		return 0
	l = 1
	l += size(root.left)
	l += size(root.right)
	return l

def isbst(root, mini=float('-inf'), maxi=float('inf')):
	if root == None:
		return True
	if root.data >= maxi or root.data <= mini:
		return False
	left = isbst(root.left, mini, root.data)
	right = isbst(root.right, root.data, maxi)
	return left and right

def solve(root, target):
	mini = float('inf')
	if root == None:
		return mini
	if root.left == None and root.right == None:
		if root.data == target:
			return 1
	if isbst(root):
		l = 0
		s = su(root)
		if s == target:
			mini = min(mini, size(root))
	return min(mini, solve(root.left, target), solve(root.right, target))

class Solution:

	def minSubtreeSumBST(self, target, root):
		mini = solve(root, target)
		if mini == float('inf'):
			return -1
		else:
			return mini


class Solution:

	def minSubtreeSumBST(self, target, root):

		def solve(nd):
			nonlocal ans
			if not nd:
				return (0, True, 0, inf, -inf)
			(Lsum, Lisbst, Lcnt, Lmin, Lmax) = solve(nd.left)
			(Rsum, Risbst, Rcnt, Rmin, Rmax) = solve(nd.right)
			if not Lisbst or not Risbst or nd.data <= Lmax or (nd.data >= Rmin):
				return (0, False, 0, inf, -inf)
			su = Lsum + Rsum + nd.data
			tot = Lcnt + Rcnt + 1
			if su == target:
				ans = min(ans, tot)
			if not nd.left:
				Lmin = nd.data
			if not nd.right:
				Rmax = nd.data
			return (su, True, tot, Lmin, Rmax)
		ans = inf
		solve(root)
		return ans if ans != inf else -1


import sys

class Solution:

	class Subtreedata:

		def __init__(self, nodeMin, nodeMax, nodeSum, countNode, isBST):
			self.nodeMin = nodeMin
			self.nodeMax = nodeMax
			self.nodeSum = nodeSum
			self.countNode = countNode
			self.isBST = isBST

	def minSubtree(self, root, target):
		global mn
		if root is None:
			returnitem = self.Subtreedata(None, None, 0, 0, 1)
			return returnitem
		else:
			left = self.minSubtree(root.left, target)
			right = self.minSubtree(root.right, target)
			curr = self.Subtreedata(None, None, 0, 0, 0)
			curr.nodeMin = root.data
			if left.nodeMin:
				curr.nodeMin = min(left.nodeMin, curr.nodeMin)
			if right.nodeMin:
				curr.nodeMin = min(right.nodeMin, curr.nodeMin)
			curr.nodeMax = root.data
			if left.nodeMax:
				curr.nodeMax = max(left.nodeMax, curr.nodeMax)
			if right.nodeMax:
				curr.nodeMax = max(right.nodeMax, curr.nodeMax)
			curr.nodeSum = left.nodeSum + right.nodeSum + root.data
			curr.countNode = left.countNode + right.countNode + 1
			if left.isBST == 1 and right.isBST == 1:
				leftcheck = True
				if left.nodeMax:
					if root.data <= left.nodeMax:
						leftcheck = False
				rightcheck = True
				if right.nodeMin:
					if root.data >= right.nodeMin:
						rightcheck = False
				if rightcheck and leftcheck:
					curr.isBST = 1
			if curr.isBST == 1 and curr.nodeSum == target:
				mn = curr.countNode
			return curr

	def minSubtreeSumBST(self, target, root):
		global mn
		mn = sys.maxsize
		self.minSubtree(root, target)
		if mn == sys.maxsize:
			mn = -1
		return mn


class Solution:

	def __init__(self):
		self.min_len = float('inf')

	def is_bst(self, node, min_val, max_val):
		if not node:
			return True
		if not min_val < node.data < max_val:
			return False
		return self.is_bst(node.left, min_val, node.data) and self.is_bst(node.right, node.data, max_val)

	def get_sum(self, node, target):
		if not node:
			return 0
		return node.data + self.get_sum(node.left, target) + self.get_sum(node.right, target)

	def traverse(self, node, target):
		if not node:
			return
		if self.is_bst(node, float('-inf'), float('inf')):
			curr_sum = self.get_sum(node, target)
			if curr_sum == target:
				self.min_len = min(self.min_len, self.get_len(node))
		self.traverse(node.left, target)
		self.traverse(node.right, target)

	def get_len(self, node):
		if not node:
			return 0
		return 1 + self.get_len(node.left) + self.get_len(node.right)

	def minSubtreeSumBST(self, target, root):
		self.traverse(root, target)
		return self.min_len if self.min_len != float('inf') else -1


import math

class Solution:

	def minSubtreeSumBST(self, target, root):
		self.possibles = []

		def target_matched(root, target):
			if root is None:
				return 0
			(l, r) = (target_matched(root.left, target), target_matched(root.right, target))
			if root.data + l + r == target:
				self.possibles.append(root)
			return root.data + l + r

		def bst(root, l, r):
			if root is None:
				return True
			self.nodes += 1
			if root.data <= l or root.data >= r:
				return False
			left = bst(root.left, l, root.data)
			right = bst(root.right, root.data, r)
			return left and right
		target_matched(root, target)
		(self.minimum, self.minroot) = (math.inf, None)
		for node in self.possibles:
			self.nodes = 0
			istrue = bst(node, -math.inf, math.inf)
			if istrue:
				if self.minimum > self.nodes:
					(self.minimum, self.minroot) = (self.nodes, node)
		if self.minroot == None:
			return -1
		return self.minimum


class Solution:

	def minSubtreeSumBST(self, target, root):
		sums_to_minlength = {}
		find_bsts_and_sums(root, sums_to_minlength)
		return sums_to_minlength.get(target, -1)

def find_bsts_and_sums(node, sums_to_minlength) -> (int, bool, int, int, int):
	if node == None:
		return (0, True, None, None, 0)
	(left_sum, left_is_bst, left_min, left_max, left_len) = find_bsts_and_sums(node.left, sums_to_minlength)
	(right_sum, right_is_bst, right_min, right_max, right_len) = find_bsts_and_sums(node.right, sums_to_minlength)
	cur_sum = node.data + left_sum + right_sum
	cur_len = left_len + right_len + 1
	cur_is_bst = left_is_bst and right_is_bst
	if cur_is_bst:
		cur_is_bst = satisfies_bst_property(node.data, left_max, right_min)
	cur_min = None
	cur_max = None
	if cur_is_bst:
		best_min_len = sums_to_minlength.get(cur_sum, float('inf'))
		if cur_len < best_min_len:
			sums_to_minlength[cur_sum] = cur_len
		cur_min = node.data if left_min is None else left_min
		cur_max = node.data if right_max is None else right_max
	return (cur_sum, cur_is_bst, cur_min, cur_max, cur_len)

def satisfies_bst_property(cur_value, left_max, right_min) -> bool:
	if left_max is not None:
		if left_max >= cur_value:
			return False
	if right_min is not None:
		if right_min <= cur_value:
			return False
	return True


class Solution:

	def minSubtreeSumBST(self, target, root):
		self.target = target
		if root.data is None:
			return -1
		self.minCount = -1
		self.iterateTree(root)
		return self.minCount

	def iterateTree(self, node):
		current = node.data
		if node.left is None:
			leftSum = 0
			leftCount = 0
			leftMax = current - 1
			leftMin = current
		else:
			leftReturn = self.iterateTree(node.left)
			if leftReturn is None:
				if self.minCount != 1 and node.right is not None:
					self.iterateTree(node.right)
				return None
			(leftCount, leftSum, leftMin, leftMax, isBst) = leftReturn
			if not isBst:
				if self.minCount != 1 and node.right is not None:
					self.iterateTree(node.right)
				return None
		if self.minCount == 1:
			return None
		if node.right is None:
			rightSum = 0
			rightCount = 0
			rightMax = current
			rightMin = current + 1
		else:
			rightReturn = self.iterateTree(node.right)
			if rightReturn is None:
				return None
			(rightCount, rightSum, rightMin, rightMax, isBst) = rightReturn
			if not isBst:
				return None
		if not (leftMax < current and current < rightMin):
			return (0, 0, 0, 0, False)
		currentSum = leftSum + current + rightSum
		currentCount = leftCount + 1 + rightCount
		if currentSum == self.target:
			if self.minCount == -1 or currentCount < self.minCount:
				self.minCount = currentCount
			return None
		if currentSum > self.target:
			return None
		return (currentCount, currentSum, leftMin, rightMax, True)


class Solution:

	def bst(self, root, target, arr):
		if root.left == None and root.right == None:
			if root.data == target:
				arr[0] = 1
			return [True, root.data, root.data, root.data, 1]
		if root.left != None:
			(lisbst, lmin, lmax, lsum, llevel) = self.bst(root.left, target, arr)
		if root.right != None:
			(risbst, rmin, rmax, rsum, rlevel) = self.bst(root.right, target, arr)
		if root.right == None:
			misbst = True
			if lisbst == False:
				misbst = False
			msum = root.data + lsum
			mmax = root.data
			if mmax <= lmax:
				misbst = False
				mmax = lmax
			if misbst == True:
				if target == msum:
					arr[0] = min(arr[0], llevel + 1)
			return (misbst, lmin, mmax, msum, llevel + 1)
		elif root.left == None:
			misbst = True
			if risbst == False:
				misbst = False
			msum = root.data + rsum
			mmin = root.data
			if mmin >= rmin:
				misbst = False
				mmin = rmin
			if misbst == True:
				if target == msum:
					arr[0] = min(arr[0], rlevel + 1)
			return (misbst, mmin, rmax, msum, rlevel + 1)
		else:
			misbst = True
			if risbst == False or lisbst == False:
				misbst = False
			msum = root.data + rsum + lsum
			k = root.data
			if k >= rmin or k <= lmax:
				misbst = False
			if misbst == True:
				if target == msum:
					arr[0] = min(arr[0], llevel + rlevel + 1)
			return (misbst, lmin, rmax, msum, llevel + rlevel + 1)

	def minSubtreeSumBST(self, target, root):
		k = 10 ** 9
		arr = [k]
		self.bst(root, target, arr)
		if arr[0] == k:
			return -1
		else:
			return arr[0]


class Solution:

	def helper(self, root, target):
		if root == None:
			return (True, False, 0, float('inf'), float('-inf'), 0)
		(is_bstl, is_targetl, l, minl, maxl, ll) = self.helper(root.left, target)
		(is_bstr, is_targetr, r, minr, maxr, lr) = self.helper(root.right, target)
		if is_targetl and is_targetr:
			return (True, True, target, min(minl, minr), max(maxl, maxr), min(ll, lr))
		elif is_targetl or is_targetr:
			return (True, True, target, min(minl, minr), max(maxl, maxr), ll if is_targetl else lr)
		s = l + r + root.data
		if is_bstl and is_bstr:
			if s == target:
				if maxl < root.data < minr:
					return (True, True, s, min(minl, minr, root.data), max(maxl, maxr, root.data), ll + lr + 1)
				else:
					return (False, False, s, min(minl, minr, root.data), max(maxl, maxr, root.data), ll + lr + 1)
			elif maxl < root.data < minr:
				return (True, False, s, min(minl, minr, root.data), max(maxl, maxr, root.data), ll + lr + 1)
			else:
				return (False, False, s, min(minl, minr, root.data), max(maxl, maxr, root.data), ll + lr + 1)
		return (False, False, s, 0, 0, 0)

	def minSubtreeSumBST(self, target, root):
		r = self.helper(root, target)
		if r[1]:
			return r[-1]
		else:
			return -1


class Solution:

	def minSubtreeSumBST(self, target, root):
		best = [1e+100]

		def dfs(root, target):
			if root.left == None and root.right == None:
				if root.data == target:
					best[0] = min(best[0], 1)
				return (True, root.data, root.data, root.data, 1)
			left = dfs(root.left, target) if root.left else (True, 0, 1e+100, -1e+100, 0)
			right = dfs(root.right, target) if root.right else (True, 0, 1e+100, -1e+100, 0)
			isBST = left[0] and right[0] and (left[3] < root.data) and (right[2] > root.data)
			s = root.data + left[1] + right[1]
			mini = min([root.data, left[2], right[2]])
			maxi = max([root.data, left[3], right[3]])
			n = 1 + left[4] + right[4]
			if s == target and isBST:
				best[0] = min(best[0], n)
			return (isBST, s, mini, maxi, n)
		dfs(root, target)
		if best[0] >= 1e+100:
			return -1
		return best[0]


class Solution:

	def isbst(self, root, mini=-999999999, maxi=999999999):
		if root == None:
			return True
		if root.data >= maxi or root.data <= mini:
			return False
		return self.isbst(root.left, mini, root.data) and self.isbst(root.right, root.data, maxi)

	def size(self, root):
		if root == None:
			return 0
		l = 1
		l += self.size(root.left)
		l += self.size(root.right)
		return l

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

	def fun(self, root, t):
		mini = 999999999
		if root == None:
			return mini
		if self.isbst(root) and self.sum(root) == t:
			mini = min(mini, self.size(root))
		l = self.fun(root.left, t)
		r = self.fun(root.right, t)
		return min(mini, l, r)

	def minSubtreeSumBST(self, target, root):
		res = self.fun(root, target)
		if res == 999999999:
			return -1
		return res


class Solution:

	def minSubtreeSumBST(self, target, root):
		ans = float('inf')

		def func(root):
			nonlocal ans
			if not root:
				return (2, 0, None, None, 0)
			(lbst, lsum, lmin, lmax, lsize) = func(root.left)
			(rbst, rsum, rmin, rmax, rsize) = func(root.right)
			if (lbst == 2 or (lbst == 1 and root.data > lmax)) and (rbst == 2 or (rbst == 1 and root.data < rmin)):
				s = root.data + lsum + rsum
				size = lsize + rsize + 1
				if s == target:
					ans = min(ans, size)
				return (1, s, lmin if lmin else root.data, rmax if rmax else root.data, size)
			return (0, None, None, None, None)
		func(root)
		return ans if ans != float('inf') else -1


class Solution:

	def check(self, node, mini, maxi):
		if node is None:
			return True
		if node.data < mini or node.data > maxi:
			return False
		return self.check(node.left, mini, node.data - 1) and self.check(node.right, node.data + 1, maxi)

	def solve(self, root, ans, target, k):
		maxi = 4294967296
		mini = -4294967296
		if root == None:
			return (0, 0)
		(left, l) = self.solve(root.left, ans, target, k)
		(right, r) = self.solve(root.right, ans, target, k)
		if left + right + root.data == target and self.check(root, mini, maxi) == True:
			if self.s > l + r + 1:
				self.s = l + 1 + r
		return (left + right + root.data, l + r + 1)

	def minSubtreeSumBST(self, target, root):
		self.s = 10000
		(ans, s) = self.solve(root, 0, target, 0)
		if self.s == 10000:
			return -1
		return self.s


class Solution:

	def check(self, root, left, right):
		if root == None:
			return True
		if left >= root.data or right <= root.data:
			return False
		return self.check(root.left, left, root.data) and self.check(root.right, root.data, right)

	def recur(self, root, target, ans):
		if root == None:
			return (0, 0)
		(lc, l) = self.recur(root.left, target, ans)
		(rc, r) = self.recur(root.right, target, ans)
		(count, val) = (lc + rc + 1, l + r + root.data)
		if val == target:
			if self.check(root, float('-inf'), float('inf')):
				ans[0] = min(ans[0], count)
		return (count, val)

	def minSubtreeSumBST(self, target, root):
		ans = [float('inf')]
		self.recur(root, target, ans)
		if ans[0] == float('inf'):
			return -1
		return ans[0]


class Solution:

	def minSubtreeSumBST(self, target, root):

		def _solve(ji):
			nonlocal ans
			if not ji:
				return (0, True, 0, inf, -inf)
			(a1, a2, a3, a4, a5) = _solve(ji.left)
			(b1, b2, b3, b4, b5) = _solve(ji.right)
			if not a2 or not b2 or ji.data <= a5 or (ji.data >= b4):
				return (0, False, 0, inf, -inf)
			sum = a1 + b1 + ji.data
			total = a3 + b3 + 1
			if sum == target:
				ans = min(ans, total)
			if not ji.left:
				a4 = ji.data
			if not ji.right:
				b5 = ji.data
			return (sum, True, total, a4, b5)
		ans = inf
		_solve(root)
		return ans if ans != inf else -1


class Solution:
	minTargetLen = None
	target = None

	def subtreeLenWithSum(self, root):
		length = 1
		treeSum = root.data
		treeMin = root.data
		treeMax = root.data
		leftBst = True
		rightBst = True
		if root.left is not None:
			(leftLength, leftTreeSum, leftTreeMin, leftTreeMax, leftTreeBst) = self.subtreeLenWithSum(root.left)
			length += leftLength
			treeSum += leftTreeSum
			treeMin = min(treeMin, leftTreeMin)
			treeMax = max(treeMax, leftTreeMax)
			if not leftTreeBst or leftTreeMax > root.data:
				leftBst = False
		if root.right is not None:
			(rightLength, rightTreeSum, rightTreeMin, rightTreeMax, rightTreeBst) = self.subtreeLenWithSum(root.right)
			length += rightLength
			treeSum += rightTreeSum
			treeMin = min(treeMin, rightTreeMin)
			treeMax = max(treeMax, rightTreeMax)
			if not rightTreeBst or rightTreeMin <= root.data:
				rightBst = False
		isBst = leftBst and rightBst
		if isBst and treeSum == self.target:
			if self.minTargetLen is None:
				self.minTargetLen = length
			if length < self.minTargetLen:
				self.minTargetLen = length
		return (length, treeSum, treeMin, treeMax, isBst)

	def minSubtreeSumBST(self, target, root):
		self.target = target
		self.subtreeLenWithSum(root)
		if self.minTargetLen is None:
			return -1
		else:
			return self.minTargetLen


import sys

class BSTCheck:

	def __init__(self):
		self.bsum = 0

	def isValidBST(self, root, rangeMin, rangeMax):
		if root is None:
			return 1
		if root.data < rangeMin or root.data > rangeMax:
			return 0
		self.bsum += root.data
		l = self.isValidBST(root.left, rangeMin, root.data - 1)
		r = self.isValidBST(root.right, root.data + 1, rangeMax)
		return l and r

	def isBST(self, root):
		self.bsum = 0
		return self.isValidBST(root, -sys.maxsize, sys.maxsize)

class Solution:

	def traverse_io(self, root, target, stack):
		if root is None:
			return
		stack.append([root.data, root])
		self.traverse_io(root.left, target, stack)
		if root.left is None and root.right is None:
			__s = 0
			for i in range(len(stack) - 1, -1, -1):
				__s += stack[i][0]
				if __s == target[0]:
					bsc = BSTCheck()
					if bsc.isBST(stack[i][1]) and bsc.bsum == target[0]:
						num = len(stack) - i
						if target[1] > num:
							target[1] = num
							target[2] = stack[i][1]
							break
				elif __s > target[0]:
					break
		self.traverse_io(root.right, target, stack)

	def minSubtreeSumBST(self, target, root):
		lo_target = [target, sys.maxsize, None]
		stack = []
		self.traverse_io(root, lo_target, stack)
		if lo_target[1] < sys.maxsize:
			bsc = BSTCheck()
			if bsc.isBST(lo_target[2]):
				return lo_target[1]
		return -1


def isBST(node):
	return isBSTUtil(node, -10000000.0, 10000000.0)

def isBSTUtil(node, mini, maxi):
	if node is None:
		return True
	if node.data < mini or node.data > maxi:
		return False
	return isBSTUtil(node.left, mini, node.data - 1) and isBSTUtil(node.right, node.data + 1, maxi)

class Solution:

	def minSubtreeSumBST(self, target, root):
		sub_root = None

		def recur(root):
			nonlocal sub_root
			if not root:
				return 0
			left = recur(root.left)
			right = recur(root.right)
			cur = left + root.data + right
			if cur == target:
				if isBST(root):
					sub_root = root
			return cur
		count = 0

		def count_nodes(root):
			if not root:
				return
			count_nodes(root.left)
			nonlocal count
			count += 1
			count_nodes(root.right)
		recur(root)
		if not sub_root:
			return -1
		count_nodes(sub_root)
		return count


from collections import deque

class Solution:

	def minSubtreeSumBST(self, target, root):

		def is_bst(node):
			return _is_bst(node, float('-inf'), float('inf'))

		def _is_bst(node, lo, hi):
			if not node:
				return 0
			if not lo < node.data <= hi:
				return -1
			left_count = _is_bst(node.left, lo, node.data)
			right_count = _is_bst(node.right, node.data, hi)
			if left_count < 0 or right_count < 0:
				return -1
			else:
				return left_count + 1 + right_count

		def find_subtree_with_sum(node, target, acc):
			if not node:
				return (0, acc)
			(left_sum, acc) = find_subtree_with_sum(node.left, target, acc)
			(right_sum, acc) = find_subtree_with_sum(node.right, target, acc)
			node_sum = left_sum + node.data + right_sum
			if node_sum == target:
				acc.append(node)
			return (node_sum, acc)
		(_, targets) = find_subtree_with_sum(root, target, [])
		bst_sizes = map(lambda node: is_bst(node), targets)
		bst_sizes = filter(lambda size: size >= 0, bst_sizes)
		bst_sizes = list(bst_sizes)
		if not bst_sizes:
			return -1
		return min(bst_sizes)


class Solution:
	length = int(1000000000.0)

	@staticmethod
	def isBST(root, target):
		if Solution.isBSTUtil(root, float('-inf'), float('inf')):
			if Solution.findSum(root) == target:
				Solution.length = min(Solution.length, Solution.findLength(root))
		if root.left is not None:
			Solution.isBST(root.left, target)
		if root.right is not None:
			Solution.isBST(root.right, target)

	@staticmethod
	def isBSTUtil(root, min_val, max_val):
		if root is None:
			return True
		if root.data <= min_val or root.data >= max_val:
			return False
		return Solution.isBSTUtil(root.left, min_val, root.data) and Solution.isBSTUtil(root.right, root.data, max_val)

	@staticmethod
	def findSum(root):
		if root is None:
			return 0
		l_sersum = Solution.findSum(root.left)
		r_sersum = Solution.findSum(root.right)
		return l_sersum + r_sersum + root.data

	@staticmethod
	def findLength(root):
		if root is None:
			return 0
		l_len = Solution.findLength(root.left)
		r_len = Solution.findLength(root.right)
		return l_len + r_len + 1

	@staticmethod
	def minSubtreeSumBST(target, root):
		Solution.length = int(1000000000.0)
		Solution.isBST(root, target)
		if Solution.length == int(1000000000.0):
			return -1
		return Solution.length


class Solution:

	def checker(self, node, lBound, uBound):
		if not node:
			return True
		if node.data > uBound or node.data < lBound:
			return False
		return self.checker(node.left, lBound, node.data - 1) and self.checker(node.right, node.data + 1, uBound)

	def helper(self, node, target):
		if not node:
			return (0, 0)
		(lval, ldep) = self.helper(node.left, target)
		(rval, rdep) = self.helper(node.right, target)
		if node.data + rval + lval == target and self.checker(node, -2147483647, 2147483647):
			self.minDepth = min(self.minDepth, ldep + rdep + 1)
		return (node.data + rval + lval, ldep + rdep + 1)

	def minSubtreeSumBST(self, target, root):
		self.minDepth = 10001
		self.helper(root, target)
		return -1 if self.minDepth == 10001 else self.minDepth


class Solution:

	def minSubtreeSumBST(self, target, root):
		ans = +float('inf')
		c = 0
		l = [root]
		i = 1
		list1 = []
		s = 0
		while i > 0:
			if l[0] != None:
				l.append(l[0].left)
				l.append(l[0].right)
				i += 2
				list1.append(l.pop(0))
				i -= 1
			else:
				l.pop(0)
				i -= 1

		def check_bst(root):
			nonlocal l
			l = []

			def bst(root):
				nonlocal l
				if root != None:
					bst(root.left)
					l.append(root.data)
					bst(root.right)
			bst(root)
			n = len(l)
			for i in range(n - 1):
				if l[i + 1] <= l[i]:
					return False
			return True

		def sum1(root):
			nonlocal c
			if root == None:
				return 0
			else:
				c += 1
				return root.data + sum1(root.left) + sum1(root.right)
		for i in list1:
			c = 0
			s = sum1(i)
			if s == target and check_bst(i):
				if ans > c:
					ans = c
		if ans != +float('inf'):
			return ans
		return -1


import sys

class Node:

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

class Solution:

	def __init__(self):
		self.ans = sys.maxsize
		self.tar = 0

	def dfs(self, node):
		if not node:
			return [0, 0, True, sys.maxsize, -sys.maxsize]
		left = self.dfs(node.left)
		right = self.dfs(node.right)
		flag = left[2] and right[2] and (left[4] < node.data) and (right[3] > node.data)
		sum = left[0] + right[0] + node.data
		nodes = left[1] + right[1] + 1
		mn = min(left[3], node.data)
		mx = max(right[4], node.data)
		if flag and sum == self.tar:
			self.ans = min(self.ans, nodes)
		return [sum, nodes, flag, mn, mx]

	def minSubtreeSumBST(self, target, root):
		self.tar = target
		self.dfs(root)
		return -1 if self.ans == sys.maxsize else self.ans