## Nth Smallest Item In Binary Search Tree

### February 24, 2017

A binary search tree is a binary tree in which all nodes in the left subtree are less than the current node and all nodes in the right subtree are greater than the current node. Items arrive in random order, are inserted into the binary search tree, and an in-order traversal produces the items in ascending order.

Your task is to write a program that finds the *n*th smallest item in a binary search tree, without enumerating all of the items in the tree. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

In Common Lisp. Here is a trivial solution. Here nth-element is O(n). To obtain a solution in O(log(n)), we could add an index to the node, and use an insertion function to build a balanced tree O(log(n)), and a function to update the indices (O(n)).

I managed to find a version of a Python-like generator mechanism in Scheme that I wrote some years back. This can turn any code that calls a given procedure repeatedly into a procedure that returns the successive values on demand. Here that code is the inorder walk which can then be run step by step.

Test results show the full inorder traversal and then each value obtained by running a similar walk to generate only the desired number of values:

@Jussi: There is a generator in the Standard Prelude.

@Praxis, here’s a comparison where I use first my generator, then your Standard Prelude define-generator to display the first two values from a separately implemented inorder traversal (from my previous entry above). First I thought you would need to wrap your yield keyword in a lambda, whereas I don’t have any keywords at all:

but then I realized that there are no restrictions to where in the body it can occur, and indeed this works:

Nice.

Same in Python. It’s more colourful, but there’s no way to just use an existing higher-order traversal for this. There would also be no way to implement the generator-function mechanism if it wasn’t built in. On the other hand, it is built in. And the “yield from” feature was added when the need was felt.

A solution in Racket.