🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏| JAVA | C | C++ | PYTHON| JAVASCRIPT | DART 
IntuitionThe problem is to find the k-th smallest element in a binary search tree (BST). Since a BST is structured such that the left subtree contains values le
![image.png](https://assets.leetcode.com/users/images/8a036fa3-6e07-45f8-9c6e-4347e1bbe1de_1738492190.6308687.png)

---
![1000080095.png](https://assets.leetcode.com/users/images/1d833154-73b3-4550-a6af-7df07cfd99e8_1738493422.1215768.png)

---



## Intuition
The problem is to find the k-th smallest element in a binary search tree (BST). Since a BST is structured such that the left subtree contains values less than the parent node and the right subtree contains values greater than the parent node, an in-order traversal of the tree will yield the elements in sorted order. My initial thought is to perform an in-order traversal and count the nodes until we reach the k-th one.

## Approach
1. **In-Order Traversal**:
   - Use a recursive helper function to perform an in-order traversal of the BST.
   - Maintain a counter (`count`) to track how many nodes have been visited.

2. **Base Cases**:
   - If the current node is null, return null.
   - Recursively traverse the left subtree first.
   - After returning from the left subtree, increment the counter.
   - If the counter equals `k`, return the current node as it represents the k-th smallest element.
   - If not, proceed to traverse the right subtree.

3. **Return Result**:
   - The main function (`kthSmallest`) calls this helper function and returns the value of the k-th smallest node found.

### Code Examples


```cpp []
#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int count = 0; // Counter for visited nodes

    int kthSmallest(TreeNode* root, int k) {
        TreeNode* result = helper(root, k);
        return result ? result->val : 0; // Return value or 0 if not found
    }

    TreeNode* helper(TreeNode* root, int k) {
        if (root == nullptr) return nullptr;

        // Traverse left subtree
        TreeNode* left = helper(root->left, k);
        if (left != nullptr) return left; // If found in left subtree

        count++; // Increment count for current node
        if (count == k) return root; // Found k-th smallest

        // Traverse right subtree
        return helper(root->right, k);
    }
};
```


```java []
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int count = 0; // Counter for visited nodes

    public int kthSmallest(TreeNode root, int k) {
        TreeNode result = helper(root, k);
        return result != null ? result.val : 0; // Return value or 0 if not found
    }

    private TreeNode helper(TreeNode root, int k) {
        if (root == null) return null;

        // Traverse left subtree
        TreeNode left = helper(root.left, k);
        if (left != null) return left; // If found in left subtree

        count++; // Increment count for current node
        if (count == k) return root; // Found k-th smallest

        // Traverse right subtree
        return helper(root.right, k);
    }
}
```


```javascript []
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    constructor() {
        this.count = 0; // Counter for visited nodes
    }

    kthSmallest(root, k) {
        const result = this.helper(root, k);
        return result ? result.val : 0; // Return value or 0 if not found
    }

    helper(node, k) {
        if (node === null) return null;

        // Traverse left subtree
        const left = this.helper(node.left, k);
        if (left !== null) return left; // If found in left subtree

        this.count++; // Increment count for current node
        if (this.count === k) return node; // Found k-th smallest

        // Traverse right subtree
        return this.helper(node.right, k);
    }
}
```


```python []
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        self.count = 0 # Counter for visited nodes

    def kthSmallest(self, root: TreeNode, k: int) -> int:
        result = self.helper(root, k)
        return result.val if result else 0 # Return value or 0 if not found

    def helper(self, node: TreeNode, k: int) -> TreeNode:
        if not node:
            return None
        
        # Traverse left subtree
        left = self.helper(node.left, k)
        if left:
            return left # If found in left subtree
        
        self.count += 1 # Increment count for current node
        if self.count == k:
            return node # Found k-th smallest
        
        # Traverse right subtree
        return self.helper(node.right, k)
```


```dart []
class TreeNode {
  int val;
  TreeNode? left;
  TreeNode? right;
  TreeNode(this.val);
}

class Solution {
  int count = 0; // Counter for visited nodes

  int kthSmallest(TreeNode? root, int k) {
    final result = helper(root, k);
    return result?.val ?? 0; // Return value or 0 if not found
  }

  TreeNode? helper(TreeNode? node, int k) {
    if (node == null) return null;

    // Traverse left subtree
    final left = helper(node.left, k);
    if (left != null) return left; // If found in left subtree

    count++; // Increment count for current node
    if (count == k) return node; // Found k-th smallest

    // Traverse right subtree
    return helper(node.right, k);
  }
}
```

## Complexity
- **Time complexity**: $$O(n)$$ where $$n$$ is the number of nodes in the binary tree. In the worst case scenario (unbalanced tree), we may need to visit all nodes.
- **Space complexity**: $$O(h)$$ where $$h$$ is the height of the tree due to recursion stack space. In a balanced BST constructed from sorted data, $$h$$ would be $$O(\log n)$$; in a skewed tree scenario (like a linked list), it could reach up to $$O(n)$$.





---

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}


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