BST Kth Smallest

Problem

Return the k-th smallest value in a binary search tree.

Insert values in order (duplicates ignored) and run an iterative inorder traversal, which visits values in sorted order. Stop and return once the k-th node is visited; k is 1-based and valid for the tree.

Return the k-th smallest value.

Hint

An inorder traversal of a BST visits values in increasing order.

Test cases

case 1

in: [[5,3,6,2,4,1],3]

expected: 3

case 2

in: [[1],1]

expected: 1

case 3

in: [[5,3,8,1,4],4]

expected: 5

case 4

in: [[2,1,3],1]

expected: 1

Starter codePython

def bst_kth_smallest(values, k):
    # Your code here
    pass

4 test cases · run your code against them in the editor