# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

    def kthSmallest(self, root, k):

        """

        :type root: TreeNode

        :type k: int

        :rtype: int

        """

        # left first

        node = root

        nodes = []

        n = 0

        while node:

            nodes.append(node)

            node = node.left

        while nodes:

            node = nodes.pop() # min val

            n += 1

            if n == k:

                return node.val

            node = node.right

            while node:

                nodes.append(node)

                node = node.left

        return None