0ms Beats 100% |Brute Force & Optimal Approaches | Easy to Understand
IntuitionA binary search tree (BST) is structured such that for every node:
All nodes in the left subtree have values smaller than the node.
All nodes in the ri
# Intuition
A **binary search tree (BST)** is structured such that for every node:
- All nodes in the left subtree have values smaller than the node.
- All nodes in the right subtree have values larger than the node.

An **in-order traversal** (left-root-right) of a BST produces values in ascending order.

The **kth smallest element** can be found by performing an in-order traversal and stopping after visiting the kth node.
# Approach
## Brute Force Approach
- The in-order traversal of a BST yields nodes in ascending order.
- By storing the elements in a sorted list during traversal, we can directly access the kth smallest element by indexing into the list.
1. In-order Traversal:
    - Perform an in-order traversal of the BST.
    - Store all the elements in a vector (or array) during the traversal.
2. Access the kth Smallest Element:
    - Since the elements in the vector are sorted, the k-th smallest element is located at index `k-1`.
3. Implementation:
    - Use recursion to traverse the tree in the order: left subtree, root, right subtree.
    - Push each node’s value into the vector during traversal.
## Optimal Approach
1. Recursive In-Order Traversal:
    - Start with the root node.
    - Traverse the left subtree first (as smaller elements are found there).
    - Decrement k as you visit each node. When k == 0, the current node is the kth smallest element.
    - If not found in the left subtree or the current node, continue to the right subtree.
2. Optimization with Early Exit:
    - If k becomes 0 during the traversal, immediately return the current node's value and stop further traversal.
3. Key Implementation Details:
    - Pass k by reference to ensure the decrement affects the recursive calls.
    - Use a base case to handle null nodes by returning a default value (-1 in this case).

# Complexity
### Brute Force Approach
**Time complexity:****Bold**
1. In-order Traversal:
Visits every node once, so the time complexity is O(n), where n is the number of nodes in the BST.
2. Access kth Smallest:
Direct indexing in the vector takes `O(1)`.
3. Overall: `O(n)`.

**Space complexity:**
1. Auxiliary Space:
The vector stores all n nodes, so the space complexity is O(n).
2. Recursion Stack:
The recursion depth depends on the height of the tree:
    - For a balanced BST: O(logn).
    - For an unbalanced BST: O(n).
3. Overall: O(n).
### Optimal Approach
**Time complexity:**
- **Best Case (Early Exit):**
    - If the kth smallest element is in the leftmost part of the tree, the traversal stops early.
Complexity: `𝑂(𝑘)`, where `𝑘` is the depth of traversal.
- **Worst Case:**
    - In the worst case, all nodes need to be traversed (if 𝑘= total nodes). 
    - For a balanced BST with 𝑛 nodes, traversal takes `𝑂(n)`.

**Space complexity:**
- The recursive stack depth depends on the height of the tree:
    - For a balanced BST, the height is `O(log n)`.
    - For an unbalanced BST (worst case), the height is `O(n)`.
- No additional space is used apart from the recursion stack.



# Code
```cpp []
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
// Optimal Approach
class Solution {
public:
    int Kth_val(TreeNode* root, int &k){
        if(root==NULL || k==0) return -1;
        int left = Kth_val(root->left,k);
        if (k==0) return left;
        k--;
        if (k==0) return root->val;
        return Kth_val(root->right,k);
    }
    int kthSmallest(TreeNode* root, int k) {
        // int kval=0;
        return Kth_val(root, k);
    }
};
```

```cpp []
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
// Brute Force Approach
class Solution {
public:
    void inorder(TreeNode* root, vector<int> &v){
        if (root==NULL) return;
        inorder(root->left, v);
        v.push_back(root->val);
        inorder(root->right, v);
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> v;
        inorder(root, v);
        return v[k-1];
    }
};
```

# Don't forget to upvote 👍
['Backtracking', 'Tree', 'Depth-First Search', 'Binary Search Tree', 'Recursion', 'Binary Tree', 'C++']