Kth Smallest in BST

Find the k-th smallest value in a binary search tree using an in-order traversal.

bst inorder recursion tree

Given the root node of a Binary Search Tree (BST) and an integer k (1-indexed), write a function `kth_smallest(root, k)` that returns the k-th smallest value in the BST. The tree is defined as:

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

You can assume:
- The tree will have at least k nodes.
- All node values are unique.
- k is between 1 and the total number of nodes.

Your solution should perform an in-order traversal (left, node, right) because that visits BST nodes in ascending order. Return the value at position k (1-based). You may implement it recursively or iteratively.

Constraints

- Number of nodes: 1 <= n <= 10^4
- Node values: -10^4 <= val <= 10^4
- k: 1 <= k <= n
- Complexity: O(n) time, O(h) space (h = tree height).

Example

>>> # Construct BST: root = TreeNode(3, TreeNode(1, None, TreeNode(2)), TreeNode(4))
>>> kth_smallest(root, 1)
1
>>> kth_smallest(root, 2)
2
>>> kth_smallest(root, 3)
3

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

In-order traversal of a BST gives sorted order.

Use a counter to track the number of nodes visited so far.

When the counter reaches k, record the current node's value.

You can implement it with an iterative stack to avoid recursion depth issues.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.