# nth bst value

Write a function that accepts a binary search tree and a non-negative integer n and returns the nth value in the tree.

``` \$ cat ntv.rkt
#lang racket

(require "bst.rkt")

(define (nth-value root n)

; If the given binary search tree defines a sequence of at least n
; values, return true and the nth value in the sequence (0th value
; is the smallest), otherwise return false and an undefined value.

(define (dive root values-to-go)
(if (root 'is-empty?)
(values values-to-go #f)
(let-values
(((values-left value) (dive (root 'left-child) values-to-go)))
(cond
((= values-left 0)
(values values-left value))
((= values-left 1)
(values 0 (root 'value)))
(#t
(dive (root 'right-child) (- values-left 1)))))))

(if (< n 0)
(values #f #f)
(let-values (((values-left value) (dive root (+ n 1))))
(values (= values-left 0) value))))

(require rackunit "utl.rkt" srfi/1)

(let ((n 6))
(call-with-list-permutations (iota n)
(lambda (p)
(let ((t (fold (lambda (v t) (t 'add v)) (binary-search-tree) p)))
(do ((i 0 (+ i 1))) ((>= i n) #t)
(let-values (((found value) (nth-value t i)))
(check-eq? found #t)
(check-eq? value i)))))))

\$ mzscheme ntv.rkt

\$
```