class Solution:
    def get_kth_smallest(self, node, k):
        count = self.count(node.left)

        if k <= count:
            return self.get_kth_smallest(node.left, k)
        
        elif k > count + 1:
            return self.get_kth_smallest(node.right, k - count - 1)
            
        return node.value
        
    def count(self, node):
        if not node:
            return 0
        
        return 1 + self.count(node.left) + self.count(node.right)

    def get_kth_smallest2(self, node, k):
        stack = []
        
        while node:
            stack.append(node.value)
            node = node.left
        
        while stack:
            node = stack.pop()
            k -= 1
            if k == 0:
                return node.value
            
            if node.right:
                node = node.right
                while node:
                    stack.append(node)
                    node = node.left
    
    def get_kth_smallest3(self, node, k):
        self.k = k
        self.result = None
        self.helper(node)
        return self.result
    
    def helper(self, node):
        if not node:
            return
            
        self.helper(node.left)
        
        self.k -= 1
        
        if self.k == 0:
            self.result = node.value
            return
        
        self.helper(node.right)

def get_kth_smallest(root, k):
    left_count = get_count(root.left)

    if left_count <= k:
        return get_kth_smallest(root.left, k)
    
    if left_count == k + 1:
        return root.value
    
    return get_kth_smallest(root.right, k - left_count - 1)

def get_count(root):
    if not root:
        return 0
    
    return 1 + get_count(root.left) + get_count(root.right)

def get_kth_smallest4(root, k):
    stack = []

    while root:
        stack.append(root)
        root = root.left
    
    while stack:
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.value
        
        if node.right:
            node = node.right
            while node:
                stack.append(node)
                node = node.left
    
