Solutions

# In-order traversal filling a list and returning the k-1 indexed element.
# trees

# DFS Inorder Traversal - O(n) time, O(n) space
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        lst = []
        self.inorder(root, lst)
        return lst[k-1]

    def inorder(self, node: Optional[TreeNode], lst: list[TreeNode]):
        if not node:
            return
        self.inorder(node.left, lst)
        lst.append(node.val)
        self.inorder(node.right, lst)

# Optimization: keep track of the count of nodes visited and return when we reach k.


# DFS iterative - O(n) time, O(h) space
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> 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