# # Implementation 1:
# # Build an array of elements and then access the kth element

class Solution:
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        def inorder(r):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []

        return inorder(root)[k - 1]


# Implementation 2:
# Do an inorder transversal and increment the global counter by 1 every time you encounter the
# root node. Check if count till now == the number that you are looking for
# as soon as you found

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:

        self.count = 0
        self.result = None
        self.k = k

        self.transverse(root)

        return self.result

    def transverse(self, root: Optional[TreeNode]) -> int:

        if not root:
            return

        # suppress future call stacks
        if self.result:
            return

        if not self.result:
            self.transverse(root.left)

        # suppress future call stacks
        if not self.result:
            self.count += 1
            if self.count == self.k:
                self.result = root.val
                return

        # suppress future call stacks
        if not self.result:
            self.transverse(root.right)