Given a BST and an integer K. Find the Kth Smallest element in the BST using O(1) extra space. 
Example 1:
Input:
      2
    /   \
   1     3
K = 2
Output: 2
Explanation: 2 is the 2nd smallest element in the BST
Example 2:
Input:
        2
      /  \
     1    3
K = 5
Output: -1
Explanation: There is no 5th smallest element in the BST as the size of BST is 3
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function KthSmallestElement() which takes the root of the BST and integer K as inputs and returns the Kth smallest element in the BST, if no such element exists return -1.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1<=Number of nodes<=10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''



class Solution:

    # Return the Kth smallest element in the given BST 

    def KthSmallestElement(self, root, K): 

        #code here.

Solutions:
class Solution:

	def KthSmallestElement(self, root, K):

		def Inorder(root):
			if root == None:
				return
			Inorder(root.left)
			ans.append(root.data)
			Inorder(root.right)
		ans = []
		Inorder(root)
		if K > len(ans):
			return -1
		return ans[K - 1]


class Solution:

	def KthSmallestElement(self, root, K):

		def inorder(root):
			nonlocal count, ans
			if not root:
				return
			inorder(root.left)
			count += 1
			if count == K:
				ans = root.data
			inorder(root.right)
		count = 0
		ans = -1
		inorder(root)
		return ans


class Solution:

	def util(self, root, k):
		if not root:
			return
		self.util(root.left, k)
		self.cnt += 1
		if self.cnt == k:
			self.cnt += 1
			self.ans = root.data
			return
		self.util(root.right, k)

	def KthSmallestElement(self, root, k):
		self.cnt = 0
		self.ans = -1
		self.util(root, k)
		return self.ans


class Solution:

	def util(self, root, k):
		global cnt, ans
		par = root
		while par != None:
			if par.left != None:
				temp = par.left
				while temp.right != None and temp.right != par:
					temp = temp.right
				if temp.right == None:
					temp.right = par
					par = par.left
				else:
					temp.right = None
					cnt += 1
					if cnt == k:
						ans = par.data
					par = par.right
			else:
				cnt += 1
				if cnt == k:
					ans = par.data
				par = par.right

	def KthSmallestElement(self, root, k):
		global cnt, ans
		cnt = 0
		ans = -1
		self.util(root, k)
		return ans


class Solution:

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

	def InOrder(self, root):
		l = []
		self.inorder(root, l)
		return l

	def KthSmallestElement(self, root, K):
		p = self.InOrder(root)
		p.sort()
		if K > len(p):
			return -1
		else:
			return p[K - 1]


class Solution:

	def kthelement(self, root):
		if root is None:
			return -1
		leftside = self.kthelement(root.left)
		if leftside != -1:
			return leftside
		self.K -= 1
		if self.K == 0:
			return root.data
		return self.kthelement(root.right)

	def KthSmallestElement(self, root, K):
		self.K = K
		return self.kthelement(root)


class Solution:

	def getMin(self, root, li):
		if root:
			self.getMin(root.left, li)
			li.append(root.data)
			self.getMin(root.right, li)

	def KthSmallestElement(self, root, K):
		li = []
		self.getMin(root, li)
		if K > len(li):
			return -1
		return li[K - 1]


class Solution:

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

	def KthSmallestElement(self, root, K):
		arr = []
		self.inorder(root, arr)
		if len(arr) < K:
			return -1
		return arr[K - 1]


class Solution:

	def KthSmallestElement(self, root, K):
		li = self.inorder(root, [])
		if len(li) < K:
			return -1
		else:
			return li[K - 1]

	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 KthSmallestElement(self, root, K):
		temp = root
		while temp:
			if temp.left is None:
				K -= 1
				if K == 0:
					return temp.data
				temp = temp.right
			else:
				pred = temp.left
				while pred.right and pred.right != temp:
					pred = pred.right
				if pred.right is None:
					pred.right = temp
					temp = temp.left
				else:
					pred.right = None
					K -= 1
					if K == 0:
						return temp.data
					temp = temp.right
		return -1


class Solution:

	def inorder(self, root):
		if root == None:
			return []
		return self.inorder(root.left) + [root.data] + self.inorder(root.right)

	def KthSmallestElement(self, root, K):
		li = self.inorder(root)
		if len(li) >= K:
			return li[K - 1]
		return -1


class Solution:

	def KthSmallestElement(self, root, K):
		if not root:
			return None
		stack = []
		count = 0
		while stack or root:
			while root:
				stack.append(root)
				root = root.left
			node = stack.pop()
			count += 1
			if count == K:
				return node.data
			root = node.right
		return -1


class Solution:

	def inOrder(self, root):
		res = []
		if root:
			res = self.inOrder(root.left)
			res.append(root.data)
			res = res + self.inOrder(root.right)
		return res

	def KthSmallestElement(self, root, K):
		li = self.inOrder(root)
		if len(li) >= K:
			return li[K - 1]
		return -1


class Solution:

	def inorder(self, root, ans):
		if root:
			self.inorder(root.left, ans)
			ans.append(root.data)
			self.inorder(root.right, ans)

	def KthSmallestElement(self, root, k):
		ans = []
		self.inorder(root, ans)
		if k <= len(ans):
			return ans[k - 1]
		else:
			return -1


class Solution:
	count = 0
	ans = 0

	def KthSmallestElement(self, root, K):
		if root == None:
			return
		self.KthSmallestElement(root.left, K)
		self.count += 1
		if self.count == K:
			self.ans = root.data
		self.KthSmallestElement(root.right, K)
		if self.ans == 0:
			return -1
		return self.ans


class Solution:

	def KthSmallestElement(self, root, K):
		count = [0]
		return self.helper(root, K, count)

	def helper(self, root, K, count):
		if root is None:
			return -1
		result = -1
		leftSubTree = self.helper(root.left, K, count)
		if leftSubTree > 0:
			result = leftSubTree
		count[0] += 1
		if count[0] == K:
			result = root.data
		if result < 0:
			rightSubTree = self.helper(root.right, K, count)
			if rightSubTree > 0:
				result = rightSubTree
		return result


class Solution:

	def KthSmallestElement(self, root, k):
		stack = []
		while root is not None or len(stack) > 0:
			while root is not None:
				stack.append(root)
				root = root.left
			root = stack.pop()
			k -= 1
			if k == 0:
				return root.data
			root = root.right
		return -1


class Solution:

	def inorder(self, root, K):
		if root is None:
			return
		self.inorder(root.left, K)
		if K == self.count:
			self.res = root.data
			self.count += 1
			return
		else:
			self.count += 1
		self.inorder(root.right, K)

	def KthSmallestElement(self, root, K):
		self.count = 1
		self.res = -1
		self.inorder(root, K)
		return self.res


class Solution:

	def inorder(self, root):
		if root:
			self.inorder(root.left)
			self.res.append(root.data)
			self.inorder(root.right)

	def KthSmallestElement(self, root, K):
		self.res = []
		self.inorder(root)
		for i in range(len(self.res)):
			if K > len(self.res):
				return -1
			return self.res[K - 1]


class Solution:

	def KthSmallestElement(self, root, k):
		result = []
		if root is None:
			return -1
		if self.size(root) < k:
			return -1
		self._kthSmallestElement(root, k, result)
		return result[k - 1]

	def _kthSmallestElement(self, root, k, result):
		if root is None:
			return
		if len(result) == k:
			return
		self._kthSmallestElement(root.left, k, result)
		result.append(root.data)
		self._kthSmallestElement(root.right, k, result)

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


import heapq

class Solution:

	def KthSmallestElement(self, root, K):
		maxheap = []
		heapq.heapify(maxheap)

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			heapq.heappush(maxheap, -1 * root.data)
			if len(maxheap) > K:
				heapq.heappop(maxheap)
			inorder(root.right)
		inorder(root)
		if len(maxheap) > K or len(maxheap) < K:
			return -1
		return -1 * heapq.heappop(maxheap)


class Solution:

	def KthSmallestElement(self, root, k):
		s = []
		c = 0
		while s or root:
			while root:
				s.append(root)
				root = root.left
			node = s.pop()
			c += 1
			if c == k:
				return node.data
			root = node.right
		return -1


class Solution:

	def __init__(self):
		self.counter = 0

	def KthSmallestElement(self, root, k):
		return self.KthSmallestElementUtil(root, k)

	def KthSmallestElementUtil(self, root, k):
		if root is None:
			return -1
		left = self.KthSmallestElementUtil(root.left, k)
		if left != -1:
			return left
		self.counter += 1
		if self.counter == k:
			return root.data
		return self.KthSmallestElementUtil(root.right, k)


global index
index = 0
global ans
ans = -1

class Solution:

	def inorder(self, root, K):
		global index
		global ans
		if not root or ans != -1:
			return
		self.inorder(root.left, K)
		index += 1
		if index == K:
			ans = root.data
			return
		self.inorder(root.right, K)

	def KthSmallestElement(self, root, K):
		global ans
		global index
		index = 0
		ans = -1
		self.inorder(root, K)
		return ans


global index
index = 0
global ans
ans = -1
global k

class Solution:

	def inorder(self, root, K):
		global index
		global ans
		if not root or ans != -1:
			return
		self.inorder(root.left, K)
		index += 1
		if index == K:
			ans = root.data
			return
		self.inorder(root.right, K)

	def KthSmallestElement(self, root, K):
		global k
		k = K
		node = self.doomdoom(root, K)
		if node:
			return node.data
		return -1

	def doomdoom(self, root, K):
		global k
		if root == None:
			return None
		left = self.doomdoom(root.left, K)
		if left != None:
			return left
		k -= 1
		if k == 0:
			return root
		return self.doomdoom(root.right, K)


class Solution:

	def solve(self, root):
		if root is None:
			return
		self.solve(root.left)
		self.q.append(root.data)
		self.solve(root.right)

	def KthSmallestElement(self, root, K):
		self.q = []
		self.solve(root)
		if K > len(self.q):
			return -1
		return self.q[K - 1]


class Solution:

	def KthSmallestElement(self, root, K):
		i = [0, -1]

		def ino(root, K):
			if root:
				ino(root.left, K)
				i[0] = i[0] + 1
				if i[0] == K:
					i[1] = root.data
					return
				return ino(root.right, K)
		ino(root, K)
		return i[1]