# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.k = k
        self.final_ans = -1
        self.dfs(root)

        return self.final_ans

    def dfs(self, root):
        if not root:
            return 

        self.dfs(root.left)
        self.k -= 1
        if self.k == 0:
            self.final_ans = root.val
        self.dfs(root.right)

        return

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.stack = deque()
        self.to_left_bottom(root)

        while(k > 0):
            cur = node = self.stack[-1]
            if node.right is not None:
                node = node.right
                self.to_left_bottom(node)
            else:
                node = self.stack.pop()
                while self.stack and self.stack[-1].right == node:
                    node = self.stack.pop()

            k -= 1 # get one node
            if k == 0:
                return cur.val
        else:
            return -1

    def to_left_bottom(self, node):
        while(node):
            self.stack.append(node)
            node = node.left