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 $