Some operation implementations on a Binary Search Tree, done in Python.

bst.py

import unittest

class BST(object):

    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


def get_kth_smallest_keys(node, k):
    """Return, as a list, `k` smallest keys in a binary search tree rooted at `node`.

    """
    smallest = []
    _get_kth_smallest_keys(node, k, smallest)
    return smallest

def _get_kth_smallest_keys(node, k, smallest):
    """A helper function. Appends nodes to the given list, `smallest`, and stop
    when k reaches 0.

    Returns the number of nodes appended to said list.

    """
    if node is None or k == 0:
        return 0
    # first, recurse left, and we get the number of nodes appended to the list by that call
    nk = _get_kth_smallest_keys(node.left, k, smallest)
    # if that number already reduces our counter to zero, we fail fast, returning that same number
    if k - nk <= 0:
        return nk
    # otherwise, we can still append this node's key to the list
    smallest.append(node.key)
    # then we recurse right, with a counter that is less 1 (our append) and less nk (appended by the left recurse)
    nnk = _get_kth_smallest_keys(node.right, k - 1 - nk, smallest)
    # our return value is the sum of our append (1) and the appends from both recurse calls
    return nk + 1 + nnk


class BSTTest(unittest.TestCase):

    def test_smallest_keys(self):
        root = BST(10)
        root.left = BST(6)
        root.right = BST(15)
        root.left.right = BST(8)
        root.right.right = BST(20)

        self.assertEquals(get_kth_smallest_keys(root, 0), [])
        self.assertEquals(get_kth_smallest_keys(root, 1), [6])
        self.assertEquals(get_kth_smallest_keys(root, 3), [6, 8, 10])
        self.assertEquals(get_kth_smallest_keys(root, 5), [6, 8, 10, 15, 20])
        self.assertEquals(get_kth_smallest_keys(root, 6), [6, 8, 10, 15, 20])


if __name__ == '__main__':
    unittest.main()