# Definition for a binary tree node.
# 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:
        '''
        Time Complexity: O(n)
        Space Complexity: O(n)
        More precise time complexity is O(h+k), where h is height of the BST and k is given k value. Worst case h = n and k = n => O(2n) => O(n)
        1. Keep moving left until you hit none when you hit none, the previous value in the stack is the value of smallest value
        2. To find the next smallest value, go one branch to the right, and keep moving left. If the right node is none go back to parent using the stack, repeat
        '''
        node = root
        stack = [] 
        while k > 0:
            while node.left != None:
                stack.append(node)
                node = node.left
            k-=1
            if k==0:
                return node.val
            if node.right:
                node = node.right
            else:
                node = stack.pop(-1)
                node.left = None
        return node.val

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public int kthSmallest(TreeNode root, int k) {
    List<TreeNode> stack = new LinkedList<>();
    while (k > 0) {
        while (root.left != null) {
            stack.addLast(root);
            root = root.left;
        }
        k -= 1;
        if (k == 0) {
            return root.val;
        }
        if (root.right != null) {
            root = root.right;
        } else {
            root = stack.removeLast();
            root.left = null;
        }
    }
    return root.val;
}