✅✅Beats 100%🔥C++🔥Python|| 🚀🚀Super Simple and Efficient Solution🚀🚀||🔥Python🔥C++✅✅
Approach 1: Binary SearchComplexity
Time complexity: O(n2)

Space complexity: O(h)
Code⬆️👇⬆️UPVOTE it⬆️👇⬆️Approach 2: Inorder TraversalComplexity
Time complexit
# Approach 1: Binary Search
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: $$O(n^2)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(h)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
 public:
  int kthSmallest(TreeNode* root, int k) {
    const int leftCount = countNodes(root->left);
    if (leftCount == k - 1)
      return root->val;
    if (leftCount >= k)
      return kthSmallest(root->left, k);
    return kthSmallest(root->right, k - 1 - leftCount);  
  }
 private:
  int countNodes(TreeNode* root) {
    if (root == nullptr)
      return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
  }
};
```
```python []
class Solution:
  def kthSmallest(self, root: TreeNode | None, k: int) -> int:
    def countNodes(root: TreeNode | None) -> int:
      if not root:
        return 0
      return 1 + countNodes(root.left) + countNodes(root.right)

    leftCount = countNodes(root.left)
    if leftCount == k - 1:
      return root.val
    if leftCount >= k:
      return self.kthSmallest(root.left, k)
    return self.kthSmallest(root.right, k - 1 - leftCount) 
```
⬆️👇⬆️UPVOTE it⬆️👇⬆️

# Approach 2: Inorder Traversal
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: $$O(n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(h)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
 public:
  int kthSmallest(TreeNode* root, int k) {
    int ans = -1;
    int rank = 0;
    traverse(root, k, rank, ans);
    return ans;
  }

 private:
  void traverse(TreeNode* root, int k, int& rank, int& ans) {
    if (root == nullptr)
      return;
    traverse(root->left, k, rank, ans);
    if (++rank == k) {
      ans = root->val;
      return;
    }
    traverse(root->right, k, rank, ans);
  }
};
```
```python []
class Solution:
  def kthSmallest(self, root: TreeNode | None, k: int) -> int:
    rank = 0
    ans = 0
    def traverse(root: TreeNode | None) -> None:
      nonlocal rank
      nonlocal ans
      if not root:
        return
      traverse(root.left)
      rank += 1
      if rank == k:
        ans = root.val
        return
      traverse(root.right)
    traverse(root)
    return ans
```
⬆️👇⬆️UPVOTE it⬆️👇⬆️

# Approach 3: Stack
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: $$O(n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(h)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
# Code
```cpp []
class Solution {
 public:
  int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> stack;
    while (root != nullptr) {
      stack.push(root);
      root = root->left;
    }
    for (int i = 0; i < k - 1; ++i) {
      root = stack.top(), stack.pop();
      root = root->right;
      while (root != nullptr) {
        stack.push(root);
        root = root->left;
      }
    }
    return stack.top()->val;
  }
};
```
```python []
class Solution:
  def kthSmallest(self, root: TreeNode | None, k: int) -> int:
    stack = []
    while root:
      stack.append(root)
      root = root.left
    for _ in range(k - 1):
      root = stack.pop()
      root = root.right
      while root:
        stack.append(root)
        root = root.left
    return stack[-1].val
```
⬆️👇⬆️UPVOTE it⬆️👇⬆️

['Tree', 'Depth-First Search', 'Binary Search Tree', 'Binary Tree', 'C++', 'Python3']