Given a BST and an integer. Find the least absolute difference between any node value of the BST and the given integer.
Example 1:
Input:
        10
      /   \
     2    11
   /  \ 
  1    5
      /  \
     3    6
      \
       4
K = 13
Output: 
2
Explanation: K=13. The node that has
value nearest to K is 11. so the answer
is 2
Example 2:
Input:
      8
    /   \
   1     9
    \     \
     4    10
    /
   3
K = 9
Output: 
0
Explanation: K=9. The node that has
value nearest to K is 9. so the answer
is 0.
Your Task:
You don't need to read input or print anything. Your task is to complete the function minDiff() that takes the root of the BST and an integer K as its input and returns the minimum absolute difference between any node value of the BST and the integer K.
Expected Time Complexity: O(Height of the BST).
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1 <= Number of nodes <= 10^{5
}1 <= Value stored at nodes(data), K <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3

# Tree Node
'''
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None
'''

class Solution:
    
    #Function to find the least absolute difference between any node
    #value of the BST and the given integer.
    def minDiff(self,root, K):
        # code here

Solutions:
class Solution:
	mini = float('inf')

	def minDiff(self, root, k):
		if root:
			if root.data > k:
				temp = root.data - k
				self.mini = min(temp, self.mini)
				self.minDiff(root.left, k)
			elif root.data < k:
				temp = k - root.data
				self.mini = min(temp, self.mini)
				self.minDiff(root.right, k)
			else:
				self.mini = 0
		return self.mini


class Solution:

	def minDiff(self, root, K):
		ans = float('inf')
		while root:
			if root.data == K:
				return 0
			elif root.data > K:
				if ans > root.data - K:
					ans = root.data - K
				root = root.left
			else:
				if ans > K - root.data:
					ans = K - root.data
				root = root.right
		return ans


import sys

class Solution:

	def util(self, root, k):
		global ans
		if root == None:
			return
		if root.data == k:
			ans = min(abs(root.data - k), ans)
			return
		elif root.data < k:
			ans = min(abs(root.data - k), ans)
			self.util(root.right, k)
		else:
			ans = min(abs(root.data - k), ans)
			self.util(root.left, k)

	def minDiff(self, root, K):
		global ans
		ans = sys.maxsize
		self.util(root, K)
		return ans


import math

class Solution:

	def minDiff(self, root, K):
		if root is None:
			return math.inf
		if root.data == k:
			return 0
		if root.data > k:
			return min(root.data - k, self.minDiff(root.left, k))
		return min(k - root.data, self.minDiff(root.right, k))


class Solution:

	def minDiff(self, root, K):
		closee = root.data
		stack = [root]
		while stack:
			node = stack.pop()
			if abs(node.data - k) < abs(closee - k):
				closee = node.data
			if node.left and k < node.data:
				stack.append(node.left)
			elif node.right and k > node.data:
				stack.append(node.right)
		return abs(closee - k)


class Solution:

	def minDiff(self, root, k):
		ans = [9999999999999999999]

		def solve(root):
			if not root:
				return
			ans[0] = min(abs(root.data - k), ans[0])
			solve(root.left)
			solve(root.right)
		solve(root)
		return ans[0]


import math

class Solution:

	def minDiff(self, root, K):
		li = self.inorder(root, [])
		if K in li:
			return 0
		else:
			y = []
			for i in li:
				y.append(abs(K - i))
			return min(y)

	def inorder(self, node, a):
		if node is None:
			return
		self.inorder(node.left, a)
		a.append(node.data)
		self.inorder(node.right, a)
		return a


class Solution:

	def minDiff(self, root, K):
		if not root:
			return float('inf')
		if root.data == K:
			return 0
		if root.data > K:
			return min(abs(root.data - K), self.minDiff(root.left, K))
		return min(abs(root.data - K), self.minDiff(root.right, K))


import sys

class Solution:

	def minDiff(self, root, K):

		def check(root):
			nonlocal res
			if not root:
				return sys.maxsize
			if root.data == K:
				res = 0
			if K < root.data:
				res = min(abs(root.data - K), res)
				check(root.left)
			else:
				res = min(abs(root.data - K), res)
				check(root.right)
		res = sys.maxsize
		check(root)
		return res


import sys

class Solution:

	def minDiff(self, root, K):

		def inorder(root):
			nonlocal res
			if not root:
				return
			inorder(root.left)
			res = min(abs(root.data - K), res)
			inorder(root.right)
		res = sys.maxsize
		inorder(root)
		return res


class Solution:

	def minDiff(self, root, K):
		minimum = [float('inf')]
		self.helper(root, K, minimum)
		return minimum[0]

	def helper(self, root, K, minimum):
		if root is None:
			return
		minimum[0] = min(minimum[0], abs(root.data - K))
		if root.data == K:
			return
		elif root.data > K:
			self.helper(root.left, K, minimum)
		elif root.data < K:
			self.helper(root.right, K, minimum)


class Solution:

	def solve(self, root, k):
		if root == None:
			return
		if abs(k - root.data) < self.res:
			self.res = abs(k - root.data)
		self.solve(root.left, k)
		self.solve(root.right, k)

	def minDiff(self, root, K):
		self.res = float('inf')
		self.solve(root, K)
		return self.res


class Solution:

	def Preorder(self, root, k, ans):
		if root == None:
			return
		if abs(root.data - k) < ans[0]:
			ans[0] = abs(root.data - k)
		self.Preorder(root.left, k, ans)
		self.Preorder(root.right, k, ans)

	def minDiff(self, root, K):
		ans = [10 ** 9]
		self.Preorder(root, K, ans)
		return ans[0]


class Solution:

	def minDiff(self, root, K):
		return self._min(root, K)

	def _min(self, node, k, diff=None):
		if node is None:
			return diff
		if diff is None or abs(node.data - k) <= diff:
			diff = abs(node.data - k)
		if k == node.data:
			return 0
		if k < node.data:
			return self._min(node.left, k, diff)
		if k > node.data:
			return self._min(node.right, k, diff)


class Solution:

	def getNextMaxNode(self, currentNode, previousMax):
		if currentNode is None:
			return None
		if currentNode.data >= previousMax:
			leftSubTreeNextMax = self.getNextMaxNode(currentNode.left, previousMax)
			if leftSubTreeNextMax is not None:
				return leftSubTreeNextMax
			return currentNode
		return self.getNextMaxNode(currentNode.right, previousMax)

	def getNextMinNode(self, currentNode, previousMin):
		if currentNode is None:
			return None
		if currentNode.data <= previousMin:
			rightSubTreeNextMax = self.getNextMinNode(currentNode.right, previousMin)
			if rightSubTreeNextMax is not None:
				return rightSubTreeNextMax
			return currentNode
		return self.getNextMinNode(currentNode.left, previousMin)

	def minDiff(self, root, K):
		maxDiff = 1000000000
		nextMaxNode = self.getNextMaxNode(root, K)
		nextMinNode = self.getNextMinNode(root, K)
		if nextMaxNode is not None:
			maxDiff = abs(nextMaxNode.data - K)
		if nextMinNode is not None:
			maxDiff = min(abs(nextMinNode.data - K), maxDiff)
		return maxDiff


class Solution:

	def minDiff(self, root, K):
		ans = 10 ** 7

		def helper(root, K):
			nonlocal ans
			if root:
				ans = min(ans, abs(K - root.data))
				if K > root.data:
					helper(root.right, K)
				else:
					helper(root.left, K)
		helper(root, K)
		return ans


class Solution:

	def abs(self, k: int) -> int:
		if k < 0:
			return -1 * k
		return k

	def minDiffHelper(self, root, K, leastDiffSoFar):
		if not root:
			return leastDiffSoFar
		if self.abs(root.data - K) < leastDiffSoFar:
			leastDiffSoFar = self.abs(root.data - K)
		if K > root.data:
			return self.minDiffHelper(root.right, K, leastDiffSoFar)
		return self.minDiffHelper(root.left, K, leastDiffSoFar)

	def minDiff(self, root, K):
		return self.minDiffHelper(root, K, 10000000000)


import sys

class Solution:

	def minDiff(self, root, K):
		ans = sys.maxsize
		while root:
			if root.data == K:
				return 0
			elif root.data > K:
				ans = min(ans, root.data - K)
				root = root.left
			else:
				ans = min(ans, K - root.data)
				root = root.right
		return ans


class Solution:

	def minDiff(self, root, K):
		ans = abs(root.data - k)
		while root != None:
			ans = min(ans, abs(root.data - k))
			if root.data < k:
				root = root.right
			else:
				root = root.left
		return ans


import math

class Solution:

	def minDiff(self, root, K):
		self.m = math.inf

		def mini(root, k):
			if root is None:
				return self.m
			self.m = min(self.m, abs(root.data - k))
			mini(root.left, k)
			mini(root.right, k)
		mini(root, k)
		return self.m


class Solution:
	val = float('inf')

	def minDiff(self, root, K):
		if root == None:
			return
		self.val = min(self.val, abs(root.data - K))
		self.minDiff(root.left, K)
		self.minDiff(root.right, K)
		return self.val


class Solution:

	def minDiff(self, root, K):
		ans = [float('inf')]

		def helper(root, k, ans):
			if not root:
				return 0
			ans[0] = min(ans[0], abs(k - root.data))
			return helper(root.left, k, ans) or helper(root.right, k, ans)
		val = helper(root, k, ans)
		return ans[0]


def solve(root, k, ans):
	if root is None:
		return
	else:
		ans.data = min(ans.data, abs(root.data - k))
		solve(root.left, k, ans)
		solve(root.right, k, ans)

class Ans:
	data = 10000000.0

class Solution:

	def minDiff(self, root, K):
		ans = Ans()
		solve(root, K, ans)
		return ans.data


class Solution:

	def minDiff(self, root, k):
		re = []

		def trav(s):
			re.append(s.data)
			if s.left is not None:
				trav(s.left)
			if s.right is not None:
				trav(s.right)
		trav(root)
		m = abs(k - re[0])
		for i in re:
			m = min(m, abs(k - i))
		return m


import sys

def inorder(root, arr):
	if root is None:
		return
	inorder(root.left, arr)
	arr.append(root.data)
	inorder(root.right, arr)

class Solution:

	def minDiff(self, root, K):
		arr = []
		inorder(root, arr)
		min_abs = sys.maxsize
		for i in arr:
			min_abs = min(min_abs, abs(i - K))
		return min_abs


class Solution:

	def minDiff(self, root, K):
		curr = root
		curr_min = 2 ** 63
		while curr is not None:
			curr_min = min(abs(K - curr.data), curr_min)
			if curr_min == 0:
				return 0
			if K < curr.data:
				curr = curr.left
			elif K > curr.data:
				curr = curr.right
		return curr_min


class Solution:

	def Preorder(self, root, K):
		temp = root
		ans = 2 ** 63
		while temp != None:
			ans = min(ans, abs(K - temp.data))
			if temp.data == K:
				return 0
			elif temp.data < K:
				temp = temp.right
			else:
				temp = temp.left
		return ans

	def minDiff(self, root, K):
		val = self.Preorder(root, K)
		return val


class Solution:

	def minDiff(self, root, K):
		if not root:
			return
		val = root.data
		while root:
			if abs(K - root.data) <= abs(K - val):
				val = root.data
			if K > root.data:
				root = root.right
			elif K < root.data:
				root = root.left
			else:
				return 0
		return abs(K - val)


import sys

class Solution:

	def minDiff(self, root, K):
		(l, g) = ([-sys.maxsize - 1], [sys.maxsize + 1])

		def f(t):
			if t == None:
				return None
			if t.data == K:
				return 0
			elif t.data > K:
				g[0] = t.data
				return f(t.left)
			else:
				l[0] = t.data
				return f(t.right)
		if f(root) == 0:
			return 0
		return min(abs(K - l[0]), abs(g[0] - K))


class Solution:

	def minDiff(self, root, K):
		v = []
		self.inorder(root, v)
		v.sort()
		minn = 999999999
		for i in range(len(v)):
			if minn > abs(K - v[i]):
				minn = abs(K - v[i])
		return minn

	def inorder(self, root, v):
		if root == None:
			return
		self.inorder(root.left, v)
		v.append(root.data)
		self.inorder(root.right, v)


import math

class Solution:

	def minDiff(self, root, K):
		if not root:
			return math.inf
		if root.data == K:
			return 0
		diff = abs(root.data - K)
		if root.data < K:
			return min(diff, self.minDiff(root.right, K))
		else:
			return min(diff, self.minDiff(root.left, K))


class Solution:

	def minDiff(self, root, K):
		if not root:
			return -1
		f = self.floor(root, K)
		c = self.ceil(root, K)
		if f == -1:
			return c - K
		elif c == -1:
			return K - f
		else:
			return min(K - f, c - K)
		return (f, c)

	def floor(self, root, K):
		if not root:
			return -1
		if root.data == K:
			return root.data
		elif root.data < K:
			res = self.floor(root.right, K)
			if res == -1:
				return root.data
			else:
				return max(res, root.data)
		else:
			return self.floor(root.left, K)

	def ceil(self, root, K):
		if not root:
			return -1
		if root.data == K:
			return root.data
		elif root.data < K:
			return self.ceil(root.right, K)
		else:
			res = self.ceil(root.left, K)
			if res == -1:
				return root.data
			else:
				return min(res, root.data)


def minDiff(self, root, k):
	if root is None:
		return 999999999
	if root.data == k:
		return 0
	if root.data > k:
		return min(abs(root.data - k), self.minDiff(root.left, k))
	return min(abs(root.data - k), self.minDiff(root.right, k))

class Solution:

	def solve(self, root, K, mn):
		if root is None:
			return
		mn.append(abs(root.data - K))
		self.solve(root.left, K, mn)
		self.solve(root.right, K, mn)

	def minDiff(self, root, K):
		if root is None:
			return 999999
		if root.data == K:
			return 0
		if root.data > K:
			return min(abs(root.data - K), self.minDiff(root.left, K))
		return min(abs(root.data - K), self.minDiff(root.right, K))


class Solution:

	def solve(self, root, K, mn):
		if root is None:
			return
		mn.append(abs(root.data - K))
		self.solve(root.left, K, mn)
		self.solve(root.right, K, mn)
		return mn

	def minDiff(self, root, K):
		mn = []
		self.solve(root, K, mn)
		return min(mn)


class Solution:
	ans = -1

	def findmin(self, node, K):
		if node is None:
			return
		if abs(K - node.data) < self.ans or self.ans == -1:
			self.ans = abs(K - node.data)
		if node.data < K:
			self.findmin(node.right, K)
		else:
			self.findmin(node.left, K)

	def minDiff(self, root, K):
		self.findmin(root, K)
		return self.ans


class Solution:

	def minDiff(self, root, K):
		smaller = -float('inf')
		bigger = float('inf')

		def recursive(root, k):
			nonlocal smaller, bigger
			if root is None:
				return
			if root.data < k and smaller < root.data:
				smaller = root.data
			elif root.data >= k and root.data < bigger:
				bigger = root.data
			recursive(root.left, k)
			recursive(root.right, k)
		recursive(root, K)
		return min(K - smaller, bigger - K)
		return 0


class Solution:

	def minDiff(self, root, k):
		self.ans = 10 ** 9

		def func(root, k):
			if root is None:
				return
			func(root.left, k)
			self.ans = min(self.ans, abs(root.data - k))
			func(root.right, k)
		func(root, k)
		return self.ans


class Solution:

	def minDiff(self, root, k):
		maxi = []
		mini = []
		self.res = None

		def func(root, k):
			if root is None:
				return
			func(root.left, k)
			if root.data == k:
				self.res = 0
			elif root.data > k:
				maxi.append(root.data)
			elif root.data < k:
				mini.append(root.data)
			func(root.right, k)
		func(root, k)
		if self.res == 0:
			return 0
		elif maxi and mini:
			ans = min(abs(maxi[0] - k), abs(mini[-1] - k))
			return ans
		elif maxi:
			return abs(maxi[0] - k)
		else:
			return abs(mini[-1] - k)


class Solution:

	def minDiff(self, root, K):
		maxi = []

		def inorder(root):
			if root != None:
				inorder(root.left)
				maxi.append(root.data)
				inorder(root.right)
		inorder(root)
		t = [abs(K - i) for i in maxi]
		return min(t)


class Solution:

	def inorder(self, root):
		res = []
		q = []
		cur = root
		while True:
			if cur is not None:
				q.append(cur)
				cur = cur.left
			elif q:
				cur = q.pop()
				res.append(cur.data)
				cur = cur.right
			else:
				break
		return res

	def minDiff(self, root, K):
		ino = self.inorder(root)
		p_index = -1
		n = len(ino)
		for i in range(n):
			if ino[i] > K:
				p_index = i
				break
			elif ino[i] == K:
				return 0
		if p_index == -1:
			return K - ino[n - 1]
		if p_index > 0 and p_index < n:
			if ino[p_index] - K > K - ino[p_index - 1]:
				return K - ino[p_index - 1]
			else:
				return ino[p_index] - K
		if p_index == 0:
			return ino[p_index] - K


class Solution:

	def minDiff(self, root, K):
		if root is None:
			return
		ilst = []

		def inorder(node):
			if not node:
				return []
			inorder(node.left)
			ilst.append(node.data)
			inorder(node.right)
		inorder(root)

		def dist(x):
			return abs(x - K)
		ans = min([dist(i) for i in ilst])
		return ans


class Solution:

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

	def check(self, a, k):
		if a == None:
			return
		self.res = min(self.res, abs(a.data - k))
		if a.data <= k:
			self.check(a.right, k)
		else:
			self.check(a.left, k)

	def minDiff(self, root, K):
		self.check(root, K)
		return self.res


import sys

class Solution:
	diff = sys.maxsize

	def minDiff(self, root, K):
		if root == None:
			return 0
		self.diff = min(self.diff, abs(K - root.data))
		if root.data > K:
			self.minDiff(root.left, K)
		if root.data < K:
			self.minDiff(root.right, K)
		return self.diff


class Solution:

	def util(self, root, ans, k):
		if not root:
			return None
		if root.data == k:
			ans[0] = 0
			return None
		ans[0] = min(abs(root.data - k), ans[0])
		if root.data < k:
			self.util(root.right, ans, k)
		else:
			self.util(root.left, ans, k)

	def minDiff(self, root, K):
		ans = [float('inf')]
		self.util(root, ans, K)
		return ans[0]


class Solution:

	def fun(self, root, k, h):
		if root == None:
			return
		h.append(abs(root.data - k))
		Solution.fun(self, root.left, k, h)
		Solution.fun(self, root.right, k, h)
		return h

	def minDiff(self, root, K):
		h = []
		a = Solution.fun(self, root, K, h)
		return min(a)


class Solution:

	def minDiff(self, root, K, mi=999999):
		if root is None:
			return mi
		if mi > abs(root.data - K):
			mi = abs(root.data - K)
		if K < root.data:
			mi = self.minDiff(root.left, K, mi)
		else:
			mi = self.minDiff(root.right, K, mi)
		return mi


class Solution:

	def minDiff(self, root, K):

		def check(root, k):
			nonlocal mn
			if root == None:
				return
			mn = min(mn, abs(root.data - k))
			check(root.left, k)
			check(root.right, k)
		mn = 10 ** 9 + 7
		check(root, K)
		return mn


class Solution:

	def minDiff(self, root, k):
		diff = float('inf')
		while root:
			diff = min(diff, abs(root.data - k))
			if k < root.data:
				root = root.left
			elif k > root.data:
				root = root.right
			else:
				return 0
		return diff


class Solution:

	def minDiff(self, root, K):
		m = float('inf')

		def solve(root, k):
			nonlocal m
			if root:
				if root.data == k:
					m = 0
					return
				elif root.data > k:
					m = min(m, root.data - k)
					solve(root.left, k)
				else:
					m = min(m, k - root.data)
					solve(root.right, k)
		solve(root, k)
		return m


from math import inf

class Solution:

	def __init__(self):
		self.ans = inf

	def tr(self, root, k):
		if root == None:
			return None
		if abs(root.data - k) < abs(k - self.ans):
			self.ans = root.data
		self.tr(root.left, k)
		self.tr(root.right, k)

	def minDiff(self, root, K):
		self.tr(root, k)
		return abs(self.ans - k)


import math

class Solution:

	def __init__(self):
		self.list1 = []

	def minDiff(self, root, K):

		def traversal(root):
			nonlocal minimum
			if root == None:
				return None
			minimum = min(minimum, abs(root.data - K))
			if root.left:
				traversal(root.left)
			if root.right:
				traversal(root.right)
		minimum = math.inf
		traversal(root)
		return minimum


class Solution:
	diff = float('inf')

	def minDiff(self, r, k):
		self.d(r, k)
		return self.diff
		return 1

	def d(self, r, k):
		if r:
			if abs(k - r.data) < abs(self.diff):
				self.diff = abs(k - r.data)
			self.d(r.left, k)
			self.d(r.right, k)


class Solution:

	def minDiff(self, root, K):
		q = []
		ans = 10000000
		q.append(root)
		while q:
			node = q.pop(0)
			ans = min(ans, abs(K - node.data))
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		return ans


class Solution:

	def minDiff(self, root, K):
		b = []
		tmp = root
		Solution.bst(tmp, b)
		b.sort()
		x = K - b[0]
		for i in range(1, len(b)):
			if abs(K - b[i]) < x:
				x = abs(K - b[i])
			if K - b[i] == 0:
				return 0
		return x

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


class Solution:

	def minDiff(self, root, K):
		res = []

		def helper(node):
			if not node:
				return
			helper(node.left)
			res.append(node.data)
			helper(node.right)
		helper(root)
		mindiff = float('inf')
		for i in res:
			min_val = abs(K - i)
			mindiff = min(mindiff, min_val)
		return mindiff


class Solution:

	def minDiff(self, root, K):
		temp = root
		closest = abs(root.data - K)
		while temp:
			if abs(temp.data - K) < closest:
				closest = abs(temp.data - K)
			if temp.data < K:
				temp = temp.right
			elif temp.data > K:
				temp = temp.left
			else:
				return 0
		return closest


class Solution:

	def minDiff(self, root, K):
		arr = []

		def inorder(root, arr):
			if root == None:
				return
			inorder(root.left, arr)
			arr.append(root.data)
			inorder(root.right, arr)
		inorder(root, arr)
		c = float('inf')
		for i in range(len(arr)):
			c = min(abs(arr[i] - K), c)
		return c


class Solution:

	def minDiff(self, root, K):
		ans = 10 ** 7

		def inorder(root, k):
			nonlocal ans
			if root == None:
				return
			ans = min(ans, abs(root.data - k))
			if root.data > k:
				inorder(root.left, k)
			else:
				inorder(root.right, k)
		inorder(root, K)
		return ans


import math

class Solution:
	_min = math.inf

	def minDiff(self, root, K):
		self._min = min(abs(root.data - K), self._min)
		if root.data > K and root.left:
			return self.minDiff(root.left, K)
		elif root.data < K and root.right:
			return self.minDiff(root.right, K)
		return min(abs(root.data - K), self._min)


class Solution:

	def __init__(self):
		self.l = []

	def minDiff(self, root, K):
		self.search(root, K, list)
		if K >= self.l[-1]:
			return abs(K - self.l[-1])
		if K <= self.l[0]:
			return abs(self.l[0] - K)
		for i in range(len(self.l)):
			if self.l[i] == K:
				return 0
			if self.l[i] < K and self.l[i + 1] > K:
				return min(abs(self.l[i] - K), abs(self.l[i + 1] - K))

	def search(self, root, k, list):
		if root is None:
			return
		self.search(root.left, k, list)
		self.l.append(root.data)
		self.search(root.right, k, list)


import sys

class Solution:

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

	def minDiff(self, root, K):
		if root == None:
			return None
		self.ans = min(self.ans, abs(root.data - K))
		if root.data > K:
			self.minDiff(root.left, K)
		else:
			self.minDiff(root.right, K)
		return self.ans


class Solution:

	def minDiff(self, root, K):
		if not root:
			return

		def min1(root):
			min2 = root.data
			if root.left:
				min2 = min1(root.left)
			return min2

		def max1(root):
			max2 = root.data
			if root.right:
				max2 = max1(root.right)
			return max2

		def help(root, K):
			if not root:
				return
			val = abs(K - root.data)
			if root.right:
				if K > root.data and abs(K - min1(root.right)) <= val:
					val = help(root.right, K)
			if root.left:
				if K <= root.data and abs(K - max1(root.left)) <= val:
					val = help(root.left, K)
			if root.right and root.left:
				if K >= root.data and abs(K - min1(root.right)) >= val:
					if abs(K - max1(root.left)) <= val:
						val = help(root.left, K)
				elif K <= root.data and abs(K - max1(root.left)) >= val:
					if abs(K - min1(root.right)) <= val:
						val = help(root.left, K)
			return val
		return help(root, K)


class Solution:

	def __init__(self):
		self.list1 = []

	def minDiff(self, root, K):

		def traversal(root):
			nonlocal value, minimum
			if root == None:
				return None
			if abs(root.data - K) < minimum:
				minimum = abs(root.data - K)
				value = root.data
			if root.left:
				traversal(root.left)
			if root.right:
				traversal(root.right)
		value = None
		minimum = 999999
		traversal(root)
		return minimum


class Solution:

	def minDiff(self, root, K):
		(largest, smallest) = (-2 ** 63, 2 ** 63)

		def for_large(root, k):
			ans = 2 ** 63
			while root:
				if root.data == k:
					return k
				if root.data > k:
					ans = min(ans, root.data)
					root = root.left
				else:
					root = root.right
			return ans

		def for_small(root, k):
			ans = -2 ** 63
			while root:
				if root.data == k:
					return k
				if root.data < k:
					ans = max(ans, root.data)
					root = root.right
				else:
					root = root.left
			return ans
		(l, s) = (for_large(root, K), for_small(root, K))
		ans = min(abs(l - K), abs(K - s))
		return ans


class Solution:

	def minDiff(self, root, K):
		diff = 2 ** 31 - 1
		ans = self.calculate_diff(root, k, diff)
		return ans

	def calculate_diff(self, root, k, diff):
		if not root:
			return 2 ** 31 - 1
		diff = min(diff, abs(root.data - k))
		lt = self.calculate_diff(root.left, k, diff)
		rt = self.calculate_diff(root.right, k, diff)
		return min(diff, min(lt, rt))


class Solution:

	def minDiff(self, root, K):
		m = float('inf')

		def inner(root, K):
			nonlocal m
			if not root:
				return
			m = min(m, abs(K - root.data))
			if K > root.data:
				inner(root.right, K)
			else:
				inner(root.left, K)
		inner(root, K)
		return m


class Solution:

	def minDiff(self, root, K):
		min_diff = float('inf')

		def dfs(node):
			nonlocal min_diff
			if not node:
				return
			diff = abs(node.data - K)
			if diff < min_diff:
				min_diff = diff
			if K < node.data:
				dfs(node.left)
			else:
				dfs(node.right)
		dfs(root)
		return min_diff


import math

class Solution:

	def __init__(self):
		self.l = []
		self.level = None
		self.x = []
		self.m = -100000

	def LV(self, root, l):
		if root == None:
			return l
		l.append(root.data)
		self.LV(root.right, l)
		self.LV(root.left, l)
		return l

	def minDiff(self, root, k):
		l = []
		level = 0
		x = self.LV(root, l)
		m = 10000000000000000
		for i in x:
			m = min(abs(k - i), m)
		return m


def minDiffHelper(root, k, lastDiff):
	if root:
		df = abs(k - root.data)
		if df == 0:
			lastDiff[0] = df
			return
		if df < lastDiff[0]:
			lastDiff[0] = df
		if k < root.data:
			minDiffHelper(root.left, k, lastDiff)
		if k > root.data:
			minDiffHelper(root.right, k, lastDiff)

class Solution:

	def minDiff(self, root, K):
		l = [10000000.0]
		minDiffHelper(root, K, l)
		return l[0]


class Solution:
	maxVal = -1
	res = 10 ** 5

	def minDiff(self, root, K):
		if root:
			if abs(root.data - K) < abs(self.maxVal - K):
				self.maxVal = root.data
				self.res = abs(root.data - K)
			if K < root.data:
				self.minDiff(root.left, K)
				return self.res
			else:
				self.minDiff(root.right, K)
				return self.res
		return self.res


class Solution:

	def minDiff(self, root, K):
		ans = [10 ** 9]
		self.util(root, K, ans)
		return ans[0]

	def util(self, root, k, ans):
		if not root:
			return
		self.util(root.left, k, ans)
		if ans[0] > abs(k - root.data):
			ans[0] = abs(k - root.data)
		self.util(root.right, k, ans)


class Solution:

	def __init__(self):
		self.arr = []

	def inOrder(self, head):
		if head == None:
			return
		self.inOrder(head.left)
		self.arr.append(head.data)
		self.inOrder(head.right)

	def minDiff(self, root, K):
		self.inOrder(root)
		if K < self.arr[0]:
			return abs(K - self.arr[0])
		n = len(self.arr)
		for i in range(n - 1):
			a = self.arr[i]
			b = self.arr[i + 1]
			if K == a:
				return 0
			elif a < K and K < b:
				return min(abs(a - K), abs(b - K))
		return abs(K - self.arr[n - 1])


class Solution:

	def minDiff(self, root, k):
		q = [root]
		res = float('inf')
		while q:
			top = q.pop(0)
			res = min(res, abs(top.data - k))
			if top.left:
				q.append(top.left)
			if top.right:
				q.append(top.right)
		return res


class Solution:

	def helper(self, node, k):
		if not node:
			return
		self.res = min(self.res, abs(node.data - k))
		self.helper(node.left, k)
		self.helper(node.right, k)

	def minDiff(self, root, K):
		self.res = float('inf')
		self.helper(root, K)
		return self.res


class Solution:

	def minDiff(self, root, K):
		ans = [10000000] * 1

		def fun(root):
			if root == None:
				return
			if abs(root.data - K) < ans[0]:
				ans[0] = abs(root.data - K)
			fun(root.left)
			fun(root.right)
		fun(root)
		return ans[0]


class Solution:

	class Node:

		def __init__(self, data):
			self.right = None
			self.left = None
			self.data = data
	res = []

	def inorder(self, root, K, res):
		if root is None:
			return True
		self.inorder(root.left, K, res)
		res.append(abs(root.data - K))
		self.inorder(root.right, K, res)

	def minDiff(self, root, K):
		res = []
		self.inorder(root, K, res)
		return min(res)