[link](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)

---

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

#### Example 1:


Input: root = [3,1,4,null,2], k = 1
Output: 1

#### Example 2:


Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

#### Constraints:

- The number of nodes in the tree is n.
- 1 <= k <= n <= 104
- 0 <= Node.val <= 104

---

The code enters a loop that continues until the current node cur is None and the stack is empty. This loop is responsible for traversing the BST. Within the loop, another loop is used to traverse as far left as possible from the current node cur. It pushes each encountered node onto the stack and updates cur to its left child.

Once there are no more left children, the code reaches a leaf node or a node with no left child. At this point, it pops a node from the stack, representing the next smallest element in the BST.

The code increments the count variable and checks if it is equal to k. If count is equal to k, it means we have found the kth smallest element, so the method returns the value of the current node cur.val. If count is not equal to k, it means we haven't reached the kth smallest element yet. In this case, the code updates the current node cur to its right child and continues the traversal from there.

The outer loop continues until the stack is empty and there are no more nodes to visit.

#### Solution 1

# 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:
        count = 0
        stack = []
        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left

            cur = stack.pop()
            count += 1
            if count == k:
                return cur.val
            cur = cur.right
        

O(T): O(N)
O(S): O(N)