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.

&nbsp;
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


&nbsp;
Constraints:


	The number of nodes in the tree is n.
	1 &lt;= k &lt;= n &lt;= 104
	0 &lt;= Node.val &lt;= 104


&nbsp;
Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

# 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:
        n=0
        stack=[] # to store the elements
        cur=root # pointer to iterate
        while cur or stack:
            while cur: # used to find the left most element
                stack.append(cur)
                cur=cur.left
            cur=stack.pop() # pop the most recent element which will be the least value at that moment
            n+=1
            if n==k:
                return cur.val
            cur=cur.right
/**
 * 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;
 *     }
 * }
 */
class Solution {
    int element,count;
    
    public int kthSmallest(TreeNode root, int k) {
        inorderTraversal(root,k);
        return element;
    }
    
    
    public void inorderTraversal(TreeNode root,int k){
        if(root.left != null){
            inorderTraversal(root.left,k);
        }
        count++;
        if(count==k){
            element = root.val;
        }
        
        if(root.right != null){
            inorderTraversal(root.right,k);
        }
    }
}
class Solution {
public:
    void findInorder(TreeNode* root, vector<int> &ans) {
        if(root == NULL)
            return;

        findInorder(root->left, ans);
        ans.push_back(root->val);
        findInorder(root->right, ans);
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> ans;
        findInorder(root, ans);
        return ans[k-1];
    }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    let stack = [];
    while(root != null || stack.length > 0) {
        while(root != null){
            stack.push(root);
            root = root.left
        }
        root = stack.pop();
        if(--k == 0) break;
        root = root.right;
    };

    return root.val;
};
Kth Smallest Element in a BST