<jupyter_start><jupyter_text>Find Kth Largest Value In BST[link](https://www.algoexpert.io/questions/Find%20Kth%20Largest%20Value%20In%20BST)  My Solution<jupyter_code># This is an input class. Do not edit.
class BST:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


# O(h + k) time | O(h) space - where h is the height of the tree and k is the input parameter
def findKthLargestValueInBst(tree, k):
    # Write your code here.
    return helper(tree, k)[0]
    
def helper(node, count):
    if node is None:
        return None, count
    
    value, count = helper(node.right, count)
    if count == 0:
        return value, count
    
    count -= 1
    if count == 0:
        return node.value, count
    
    value, count = helper(node.left, count)
    if count == 0:
        return value, count
    
    return None, count<jupyter_output><empty_output><jupyter_text>Expert Solution<jupyter_code># This is an input class. Do not edit.
class BST:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


# O(n) time | O(n) space - where n is the number of nodes in the tree
def findKthLargestValueInBst(tree, k):
    sortedNodeValues = []
    inOrderTraverse(tree, sortedNodeValues)
    return sortedNodeValues[len(sortedNodeValues) - k]

def inOrderTraverse(node, sortedNodeValues):
    if node is None:
        return

    inOrderTraverse(node.left, sortedNodeValues)
    sortedNodeValues.append(node.value)
    inOrderTraverse(node.right, sortedNodeValues)
# This is an input class. Do not edit.
class BST:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class TreeInfo:
    def __init__(self, numberOfNodesVisited, latestVisitedNodeValue):
        self.numberOfNodesVisited = numberOfNodesVisited
        self.latestVisitedNodeValue = latestVisitedNodeValue

# O(n) time | O(n) space - where n is the number of nodes in the tree
def findKthLargestValueInBst(tree, k):
    treeInfo = TreeInfo(0, -1)
    reverseInOrderTraverse(tree, k, treeInfo)
    return treeInfo.latestVisitedNodeValue
    
def reverseInOrderTraverse(node, k, treeInfo):
    if node is None or treeInfo.numberOfNodesVisited >= k:
        return

    reverseInOrderTraverse(node.right, k, treeInfo)
    if treeInfo.numberOfNodesVisited < k:
        treeInfo.numberOfNodesVisited += 1
        treeInfo.latestVisitedNodeValue = node.value
        reverseInOrderTraverse(node.left, k, treeInfo)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09029089535323007, 'fraction_numerical': 0.00680015111446921, 'mean_word_length': 3.21656050955414, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '586357', 'license': 'MIT', 'n_tokens_mistral': 869, 'n_tokens_neox': 854, 'n_words': 238, 'path': 'algoExpert/find_kth_largest_value_in_bst/solution.ipynb', 'repo_name': 'maple1eaf/learning_algorithm', 'size': '2647'}