> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/binary-search-tree/8.kth-smallest-element-in-a-bst.md).

# 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)

```cpp
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)**

```cpp
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;
}
```