'''Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Example 1:

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

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?'''

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        node = root
        
        while True:
            if node != None:
                stack.append(node)
                node = node.left
            elif stack:
                node = stack.pop()
                
                k -= 1
                if k == 0:
                    return node.val
                
                node = node.right
            else:
                break
fffb7819e1ffda04cbf0931cf94f0e4200417a1e
<mask token>

<mask token>


class Solution:
    <mask token>

<mask token>


class Solution:

    def kthSmallest(self, root: TreeNode, k: int) ->int:
        stack = []
        node = root
        while True:
            if node != None:
                stack.append(node)
                node = node.left
            elif stack:
                node = stack.pop()
                k -= 1
                if k == 0:
                    return node.val
                node = node.right
            else:
                break

'''Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Example 1:

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

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?'''

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        node = root
        
        while True:
            if node != None:
                stack.append(node)
                node = node.left
            elif stack:
                node = stack.pop()
                
                k -= 1
                if k == 0:
                    return node.val
                
                node = node.right
            else:
                break