text: # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  class Solution(object):
      def kthSmallest(self, root, k):
          """
          :type root: TreeNode
          :type k: int
          :rtype: int
          """
          stack = []
          
          while True:
              while root:
                  stack.append(root)
                  root = root.left
              root = stack.pop()
              k -= 1
              if not k:
                  return root.val
              root = root.right
  
  
  class Solution(object):
      def kthSmallest(self, root, k):
          """
          :type root: TreeNode
          :type k: int
          :rtype: int
          """
          stack, result = list(), list()
          while stack or root:
              if root:
                  stack.append(root)
                  root = root.left
              else:
                  root = stack.pop()
                  result.append(root.val)
                  if len(result) == k:
                      return result[k-1]
                  root = root.right