Given a Binary search tree. Your task is to complete the function which will return the Kth largest element without doing any modification in Binary Search Tree.
Example 1:
Input:
      4
    /   \
   2     9
k = 2 
Output: 4
Example 2:
Input:
       9
        \ 
          10
K = 1
Output: 10
Your Task:
You don't need to read input or print anything. Your task is to complete the function kthLargest() which takes the root of the BST and an integer K as inputs and returns the Kth largest element in the given BST.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(H) where H is max recursion stack of height h at a given time.
Constraints:
1 <= N <= 1000
1 <= K <= N

Source: geeksforgeeks | Difficulty: EASY
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



# return the Kth largest element in the given BST rooted at 'root'

class Solution:

    def kthLargest(self,root, k):

        #your code here

Solutions:
class Solution:

	def kthLargest(self, root, k):
		a = []

		def post(node):
			if node.right:
				post(node.right)
			a.append(node.data)
			if node.left:
				post(node.left)
		post(root)
		return a[k - 1]


class Solution:

	def kthLargest(self, root, k):
		stack = []
		count = 0
		while stack or root:
			while root:
				stack.append(root)
				root = root.right
			node = stack.pop()
			count += 1
			if count == k:
				return node.data
			root = node.left


class Solution:

	def solve(self, root, k):
		if root == None:
			return
		self.solve(root.right, k)
		if self.ind == k:
			self.ans = root.data
			self.ind += 1
			return self.ans
		else:
			self.ind += 1
		self.solve(root.left, k)

	def kthLargest(self, root, k):
		self.ind = 1
		self.ans = -9999
		self.solve(root, k)
		return self.ans


class Solution:

	def kthLargest(self, root, k):

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


class Solution:

	def im(self, root, k):
		if root is None:
			return
		self.im(root.right, k)
		self.c += 1
		if self.c == k:
			self.res = root.data
		self.im(root.left, k)

	def kthLargest(self, root, k):
		self.c = 0
		self.res = -1
		self.im(root, k)
		return self.res


class Solution:

	def kthLargest(self, root, k):
		res = []

		def solve(root):
			if root == None:
				return
			solve(root.left)
			res.append(root.data)
			solve(root.right)
			return
		solve(root)
		res.sort(reverse=True)
		return res[k - 1]


class Solution:

	def kthLargest(self, root, k):
		counter = 0
		curr = root
		while curr:
			if curr.right:
				temp = curr.right
				while temp.left and temp.left != curr:
					temp = temp.left
				if temp.left:
					temp.left = None
					counter += 1
					if counter == k:
						return curr.data
					curr = curr.left
				else:
					temp.left = curr
					curr = curr.right
			else:
				counter += 1
				if counter == k:
					return curr.data
				curr = curr.left


class Solution:

	def kthLargest(self, root, k):
		counter = 0
		ans = root.data

		def traversal(root):
			nonlocal counter
			nonlocal ans
			if root.right:
				traversal(root.right)
			counter += 1
			if counter == k:
				ans = root.data
				return
			if root.left:
				traversal(root.left)
		traversal(root)
		return ans


class Solution:

	def kthLargest(self, root, k):
		count = 0
		current = root
		while current:
			if current.right == None:
				count += 1
				if count == k:
					return current.data
				current = current.left
			else:
				pre = current.right
				while pre.left and pre.left != current:
					pre = pre.left
				if pre.left == None:
					pre.left = current
					current = current.right
				else:
					pre.left = None
					count += 1
					if count == k:
						return current.data
					current = current.left


class Solution:

	def __init__(self):
		self.value = 0
		self.k = 0

	def kthLargest(self, root, k):

		def count(root):
			if root is None:
				return
			count(root.right)
			self.k -= 1
			if self.k == 0:
				self.value = root.data
				return
			count(root.left)
		self.k = k
		count(root)
		return self.value


import sys

class Solution:

	def kthLargest(self, root, k):

		def inorder(root, ret):
			if root == None:
				return
			inorder(root.left, ret)
			ret.append(root.data)
			inorder(root.right, ret)
		ret = []
		inorder(root, ret)
		return ret[len(ret) - k]


class Solution:

	def kthLargest(self, root, k):
		ans = self.inorder(root)
		return ans[::-1][k - 1]

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


class Solution:

	def kthLargest(self, root, k):
		val = []
		while True:
			while root:
				val.append(root)
				root = root.right
			node = val.pop()
			k -= 1
			if not k:
				return node.data
			root = node.left


class Solution:

	def kthLargest(self, root, k):
		global l
		l = k
		global m

		def x(node):
			global l, m
			if node:
				x(node.right)
				l -= 1
				if l == 0:
					m = node.data
					return node.data
				x(node.left)
			else:
				return None
		x(root)
		return m


class Solution:

	def kthLargest(self, root, k):
		stack = []

		def dfs(root):
			if not root:
				return None
			dfs(root.left)
			stack.append(root.data)
			dfs(root.right)
		dfs(root)
		return stack[len(stack) - k]


class Solution:

	def kthLargest(self, root, k):
		stack = [(root, False)]
		ans = []
		while stack:
			(node, visited) = stack.pop()
			if visited:
				ans.append(node.data)
			elif node:
				stack.append((node.right, False))
				stack.append((node, True))
				stack.append((node.left, False))
		return ans[len(ans) - k]


class Solution:

	def kthLargest(self, root, k):
		count = self.fn(root.right)
		if count >= k:
			return self.kthLargest(root.right, k)
		elif count + 1 < k:
			return self.kthLargest(root.left, k - count - 1)
		return root.data

	def fn(self, root):
		if not root:
			return 0
		return 1 + self.fn(root.left) + self.fn(root.right)


class Solution:

	def kthLargest(self, root, k):
		out = []

		def fn(root):
			if not root:
				return
			fn(root.left)
			out.append(root.data)
			fn(root.right)
		fn(root)
		return out[len(out) - k]


class Solution:

	def kthLargest(self, root, k):
		stack = []
		counter = 0
		while len(stack) > 0 or root:
			if root:
				stack.append(root)
				root = root.right
			else:
				node = stack.pop()
				counter += 1
				if counter == k:
					return node.data
				root = node.left


class Solution:

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

	def kthLargest(self, root, k):
		self.q = []
		self.solve(root, k)
		if self.q:
			return self.q[k - 1]
		else:
			return -1


class Solution:

	def kthLargest(self, root, k):
		li = []

		def preOrder(root, li):
			if root is None:
				return
			preOrder(root.left, li)
			li.append(root.data)
			preOrder(root.right, li)
			return
		preOrder(root, li)
		n = len(li)
		return li[n - k]


class Solution:

	def kthLargest(self, root, k):
		self.k = k
		self.res = None
		self.dfs(root)
		return self.res

	def dfs(self, node):
		if not node or self.res:
			return
		self.dfs(node.right)
		self.k -= 1
		if self.k == 0:
			self.res = node.data
			return
		self.dfs(node.left)


class Solution:

	def kthLargest(self, root, k):

		def dfs(node):
			if not node:
				return -1
			nonlocal k
			left = dfs(node.right)
			if left != -1:
				return left
			if k == 1:
				return node.data
			else:
				k -= 1
				return dfs(node.left)
		return dfs(root)


class Solution:

	def kthLargest(self, root, k):
		if root is None:
			return True
		stack = []
		current = root
		result = []
		while current or stack:
			while current:
				stack.append(current)
				current = current.left
			current = stack.pop()
			result.append(current.data)
			current = current.right
		return result[len(result) - k]


class Solution:

	def kthLargest(self, root, k):
		stack = []
		while 1:
			while root:
				stack.append(root)
				root = root.right
			if len(stack) == 0:
				break
			temp = stack.pop()
			k -= 1
			if k == 0:
				return temp.data
			root = temp.left


class Solution:

	def helper(self, root, count, res):
		if not root:
			return
		self.helper(root.right, count, res)
		count[0] -= 1
		if count[0] == 0:
			res[0] = root.data
			return
		self.helper(root.left, count, res)
		return

	def kthLargest(self, root, k):
		(count, res) = ([k], [-1])
		self.helper(root, count, res)
		return res[0]


class Solution:

	def kthLargest(self, root, k):
		p = []

		def kl(node, cnt):
			if not node:
				return None
			kl(node.left, cnt)
			p.append(node.data)
			kl(node.right, cnt)
			return node
		kl(root, 0)
		return p[len(p) - k]


class Solution:

	def kthLargest(self, root, k):
		res = []

		def dfs(node):
			if not node:
				return
			dfs(node.left)
			res.append(node.data)
			dfs(node.right)
		dfs(root)
		return res[len(res) - k]


class Solution:

	def kthLargest(self, root, k):
		q = []
		cur = root
		count = 0
		while True:
			if cur is not None:
				q.append(cur)
				cur = cur.right
			elif q:
				cur = q.pop()
				count += 1
				if count == k:
					return cur.data
				cur = cur.left
			else:
				break
		return None


class Solution:

	def kthLargest(self, root, k):
		self.length = k
		self.found = None

		def getLargest(root):
			if root is None or self.found:
				return
			getLargest(root.right)
			self.length -= 1
			if self.length == 0:
				self.found = root.data
				return
			getLargest(root.left)
		getLargest(root)
		return self.found


def slove(root, ans):
	if root is None:
		return
	slove(root.left, ans)
	ans.append(root.data)
	slove(root.right, ans)
	return ans

class Solution:

	def kthLargest(self, root, k):
		ans = []
		slove(root, ans)
		return ans[len(ans) - k]


class Solution:

	def __init__(self):
		self.counter = 0
		self.answer = 0

	def kthLargest(self, root, k):

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


class Solution:

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

	def kthLargest(self, root, k):
		res = self.inorder(root)
		return res[len(res) - k]


class Solution:

	def kthLargest(self, root, k):

		def inorder(root):
			if not root:
				return []
			return inorder(root.left) + [root.data] + inorder(root.right)
		l = inorder(root)
		return l[-k]


class Solution:

	def kthLargest(self, root, k):
		result = Solution().solve(root, [])
		return result[len(result) - k]

	def solve(self, root, result):
		if not root:
			return
		Solution().solve(root.left, result)
		result.append(root.data)
		Solution().solve(root.right, result)
		return result


class Solution:

	def kthLargest(self, root, k):
		li = self.order(root, [])
		return li[-k]

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


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 kthLargest(self, root, k):
		arr = []
		self.inorder(root, arr)
		arr = arr[::-1]
		if len(arr) < k:
			return -1
		return arr[k - 1]


class Solution:

	def solve(self, root, k):
		if root == None:
			return
		self.solve(root.right, k)
		if self.i == k:
			self.ans = root.data
			self.i += 1
			return self.ans
		else:
			self.i += 1
		self.solve(root.left, k)

	def kthLargest(self, root, k):
		self.ans = 0
		self.i = 1
		self.solve(root, k)
		return self.ans


class Solution:
	a = []

	def kthLargest(self, root, k):

		def inorder(root):
			if root:
				inorder(root.left)
				self.a.append(root.data)
				inorder(root.right)
		inorder(root)
		n = len(self.a)
		return self.a[n - k]


class Solution:

	def kthLargest(self, root, k):
		kthlargest.c = 0
		kthlargest.result = 0
		kthlargest(root, k)
		return kthlargest.result

def kthlargest(root, k):
	if root == None:
		return
	kthlargest(root.right, k)
	kthlargest.c += 1
	if kthlargest.c == k:
		kthlargest.result = root.data
		return
	kthlargest(root.left, k)


class Solution:

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

	def kthLargest(self, root, k):
		arr = []
		temp = root
		while temp:
			if temp.right is None:
				k -= 1
				if k == 0:
					return temp.data
				temp = temp.left
			else:
				pred = temp.right
				while pred.left and pred.left != temp:
					pred = pred.left
				if pred.left is None:
					pred.left = temp
					temp = temp.right
				else:
					pred.left = None
					k -= 1
					if k == 0:
						return temp.data
					temp = temp.left
		return -1


class Solution:

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

	def kthLargest(self, root, k):
		arr = self.inorder(root)
		return arr[-k]


class Solution(object):

	def kthLargest1(self, root, k):
		stack = []
		while True:
			while root:
				stack.append(root)
				root = root.right
			root = stack.pop()
			k -= 1
			if k == 0:
				return root.data
			root = root.left

	def kthLargest(self, root, k):

		def dfs(node):
			if node.right:
				dfs(node.right)
			nonlocal k, result
			k -= 1
			if k == 0:
				result = node.data
				return
			if node.left:
				dfs(node.left)
		result = None
		dfs(root)
		return result


class Solution(object):

	def kthLargest(self, root, k):
		stack = []
		while True:
			while root:
				stack.append(root)
				root = root.right
			root = stack.pop()
			k -= 1
			if k == 0:
				return root.data
			root = root.left


class Solution:

	def kthLargest(self, root, k):
		array = []
		self._klargest(root, k, array)
		return array[-1]

	def _klargest(self, node, k, array):
		if node:
			self._klargest(node.right, k, array)
			if len(array) < k:
				array.append(node.data)
			self._klargest(node.left, k, array)


class Solution:

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

	def kthLargest(self, root, k):
		ans = []
		self.inorder(root, ans)
		return ans[len(ans) - k]


class Solution:

	def __init__(self):
		self.count = 0
		self.ans = None

	def kthLargest(self, root, k):
		self.kthLargest1(root, k)
		return self.ans

	def kthLargest1(self, root, k):
		if root == None:
			return
		self.kthLargest1(root.right, k)
		if self.count < k:
			self.count += 1
			if self.count == k:
				self.ans = root.data
				return
		self.kthLargest1(root.left, k)
		return


class Solution:

	def __init__(self):
		self.arr = list()

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

	def kthLargest(self, root, k):
		self.inorder(root)
		return self.arr[-k]


class Solution:

	def kthLargest(self, root, k):
		largest = float('-inf')
		self.k = k

		def inorder(root, k):
			if root is None:
				return None
			left = inorder(root.right, k)
			self.k -= 1
			if self.k == 0:
				self.ans = root
			right = inorder(root.left, k)
		inorder(root, k)
		return self.ans.data


class Solution:

	def kthLargest(self, root, k):
		self.count = 0
		self.ans = -1

		def dfs(root):
			if not root:
				return
			dfs(root.right)
			self.count += 1
			if self.count == k:
				self.ans = root.data
				return
			dfs(root.left)
			return
		dfs(root)
		return self.ans


class Solution:

	def kthLargest(self, root, k):
		l = []
		stack = []
		while stack or root:
			if root:
				stack.append(root)
				root = root.left
			else:
				t = stack.pop()
				l.append(t.data)
				root = t.right
		return l[len(l) - k]


class Solution:

	def kthLargest(self, root, k):
		result = []
		self._kthLargest(root, k, result)
		return result[k - 1]

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


class Solution:

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


class Solution:

	def kth(self, root, k):
		if not root:
			return -1
		right = self.kth(root.right, k)
		if right != -1:
			return right
		self.d += 1
		if self.d == k:
			return root.data
		return self.kth(root.left, k)

	def kthLargest(self, root, k):
		if not root:
			return -1
		self.d = 0
		return self.kth(root, k)


class Solution:

	def kthLargest(self, root, k) -> object:
		elems = []
		self._kthLargest(root, k, elems)
		return elems[k - 1]

	def _kthLargest(self, node, k, elems: list) -> None:
		if len(elems) == k:
			return
		if node is None:
			return
		self._kthLargest(node.right, k, elems)
		elems.append(node.data)
		self._kthLargest(node.left, k, elems)


class Solution:

	def kthLargest(self, root, k):
		ans = []
		while (ans, root):
			while root:
				ans.append(root)
				root = root.right
			root = ans.pop()
			k -= 1
			if k == 0:
				return root.data
			root = root.left


class Solution:

	def kthLargest(self, root, k):
		res = []

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			res.append(root.data)
			inorder(root.right)
		inorder(root)
		if len(res) < k:
			return -1
		return res[-k]


class Solution:

	def kthLargestUtil(self, root, k):
		global c
		global res
		if root == None or c >= k:
			return
		self.kthLargestUtil(root.right, k)
		c = c + 1
		if c == k:
			res = root.data
			return
		self.kthLargestUtil(root.left, k)

	def kthLargest(self, root, k):
		global c
		global res
		c = 0
		res = -1
		self.kthLargestUtil(root, k)
		return res


class Solution:

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

	def kthLargest(self, root, k):
		d = self.inorder(root)
		return d[-k]


class Solution:

	def kthLargest(self, root, k):
		stk = []
		self.push_right(root, stk)
		while stk:
			node = stk.pop()
			k -= 1
			if k == 0:
				return node.data
			self.push_right(node.left, stk)

	def push_right(self, node, stk):
		while node:
			stk.append(node)
			node = node.right


class Solution:

	def __init__(self):
		self.index = 0
		self.ans = 0

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


class Solution:

	def __init__(self):
		self.count = 0
		self.ans = None

	def kthLargest(self, root, k):
		self.helper(root, k)
		return self.ans

	def helper(self, root, k):
		if root is None or self.count >= k:
			return
		self.helper(root.right, k)
		self.count += 1
		if self.count == k:
			self.ans = root.data
			return
		self.helper(root.left, k)


class Solution:

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

	def kthLargest(self, root, k):
		ans = self.inorder(root, [])
		n = len(ans)
		return ans[n - k]


class Solution:

	def kthLargest(self, root, k):
		curr = root
		st = []
		while True:
			while curr:
				st.append(curr)
				curr = curr.right
			curr = st.pop()
			k -= 1
			if k == 0:
				return curr.data
			curr = curr.left
		return -1


from collections import deque as dq

class Solution:

	def kthLargest(self, root, k):
		q = dq()
		ans = dq()
		if root is None:
			return
		q.append(root)
		while len(q) > 0:
			curr = q.pop()
			ans.append(curr.data)
			leftChild = curr.left
			rightChild = curr.right
			if leftChild:
				q.append(leftChild)
			if rightChild:
				q.append(rightChild)
		ans = list(set(ans))
		ans.sort()
		return ans[-k]


class Solution:

	def kthLargest(self, root, k):
		self.count = k
		self.result = 0

		def revInorder(node):
			if node is None:
				return None
			revInorder(node.right)
			self.count -= 1
			if self.count == 0:
				self.result = node.data
				return
			revInorder(node.left)
		revInorder(root)
		return self.result


class Solution:

	def kthLargest(self, root, k):
		c = []

		def che(c, root):
			if root:
				che(c, root.left)
				c.append(root.data)
				che(c, root.right)
		che(c, root)
		return c[-k]


class Solution:

	def kthLargest(self, root, k):
		res = []

		def dfs(root):
			nonlocal res
			if not root:
				return
			dfs(root.right)
			res.append(root.data)
			dfs(root.left)
		dfs(root)
		return res[k - 1]


def inorder(root):
	result = []
	stack = []
	current = root
	while True:
		if current != None:
			stack.append(current)
			current = current.left
		elif stack:
			temp = stack.pop()
			result.append(temp.data)
			current = temp.right
		elif stack == [] and current == None:
			break
	return result

class Solution:

	def kthLargest(self, root, k):
		if root == None:
			return -1
		result = inorder(root)
		return result[-1 * k]


class Solution:

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

	def kthLargest(self, root, k):
		if root:
			li = []
			self.inOrderTrav(root, li)
			return li[-k]
		else:
			return []


class Solution:

	def kthLargest(self, root, k):

		def reverseInorder(root):
			if root is None:
				return None
			right = reverseInorder(root.right)
			if reverseInorder.counter == 0:
				return right
			reverseInorder.counter -= 1
			if reverseInorder.counter == 0:
				return root
			left = reverseInorder(root.left)
			return left if left is not None else right
		reverseInorder.counter = k
		return reverseInorder(root).data


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 kthLargest(self, root, k):
		self.q = []
		self.solve(root)
		a = len(self.q) - k
		return self.q[a]


class Solution:

	def kthLargest(self, root, k):
		ans = 0

		def helper(root):
			nonlocal ans
			nonlocal k
			if not root:
				return
			helper(root.right)
			k = k - 1
			if k == 0:
				ans = root.data
				return
			helper(root.left)
		helper(root)
		return ans


class Solution:

	def kthLargest(self, root, k):
		arr = []

		def inorder(node):
			if not node:
				return
			inorder(node.left)
			arr.append(node.data)
			inorder(node.right)
		inorder(root)
		return arr[len(arr) - k]


class Solution:

	def kthLargest(self, root, k):

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			res.append(root.data)
			inorder(root.right)
		res = []
		inorder(root)
		res.reverse()
		return res[k - 1]


import heapq

class Solution:

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

	def kthLargest(self, root, k):
		self.inorder_traversal(root, self.nums)
		minh = []
		for num in self.nums:
			heapq.heappush(minh, num)
			if len(minh) > k:
				heapq.heappop(minh)
		return minh[0]

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


class Solution:

	def kthLargest(self, root, k):
		l = []

		def fun(root):
			if root:
				fun(root.left)
				l.append(root.data)
				fun(root.right)
		fun(root)
		return l[-k]


class Solution:

	def kthLargest(self, root, k):
		self.ans = 1
		self.count = 1
		self.solve(root, k)
		return self.ans

	def solve(self, root, k):
		if root is None:
			return
		self.solve(root.right, k)
		if self.count == k:
			self.ans = root.data
			self.count += 1
			return self.ans
		else:
			self.count += 1
		self.solve(root.left, k)


class Solution:
	c = 0
	ans = 0

	def findingkth(self, root, k):
		if root == None:
			return
		self.findingkth(root.right, k)
		self.c = self.c + 1
		if self.c == k:
			self.ans = root.data
		self.findingkth(root.left, k)

	def kthLargest(self, root, k):
		self.findingkth(root, k)
		return self.ans


class Solution:

	def kthLargest(self, root, k):
		c = 0
		cur = root
		while cur:
			if cur.right is None:
				c += 1
				if c == k:
					return cur.data
				cur = cur.left
			else:
				pre = cur.right
				while pre.left and pre.left != cur:
					pre = pre.left
				if pre.left is None:
					pre.left = cur
					cur = cur.right
				else:
					pre.left = None
					c += 1
					if c == k:
						return cur.data
					cur = cur.left


def check(root, lst):
	if root:
		check(root.left, lst)
		check(root.right, lst)
		lst.append(root.data)

class Solution:

	def kthLargest(self, root, k):
		lst = []
		check(root, lst)
		lst.sort(reverse=True)
		return lst[k - 1]


import heapq

def func(root, heap, k):
	if root is None:
		return
	heapq.heappush(heap, root.data)
	if len(heap) > k:
		heapq.heappop(heap)
	func(root.left, heap, k)
	func(root.right, heap, k)

class Solution:

	def kthLargest(self, root, k):
		heap = []
		func(root, heap, k)
		return heap[0]