9.Kth Smallest Element in a BST

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

Solution I :(Using Inorder Traversal)

class Solution
{
public:
    int kthSmallest(TreeNode *root, int k)
    {

        vector<int> v;

        TreeNode *t = root;
        stack<TreeNode *> s;

        while (t != NULL || !s.empty())
        {

            if (t != NULL)
            {
                s.push(t);
                t = t->left;
            }
            else
            {
                t = s.top();
                v.push_back(t->val);
                s.pop();
                t = t->right;
            }
        }

        return v[k - 1];
    }
};

Time Complexity: O(n), Space Complexity: O(n)

Solution II: (Using Traversal)

void findSmallest(Tree *root, int k, int &count, int &val)
{
    if (!root)
    {
        return;
    }

    if (count >= k) 
    {
        return;
    }

    findSmallest(root->left, k, count, val);

    if(count>=k){
        return;
    }
    
    val = root->val;
    count = count + 1;

    findSmallest(root->right, k, count, val);

    return;
}

int solve(Tree *root, int k)
{

    int count = -1;
    int val = INT_MIN;
    findSmallest(root, k, count, val);

    return val;
}