ordered list to binary tree

ordered-to-bst.rkt

#lang racket

;; The code of SICP Exercise 2.64, but rewritten to use define-values instead of let.
;; http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-16.html#%_thm_2.64
(struct tree (entry left right) #:transparent)

(define EMPTY-TREE '())

;; list->tree: (listof X) -> tree
;; Given an ordered list of elements, constructs the balanced binary tree.
(define (list->tree elements)
  (define-values (the-tree remaining)
    (partial-tree elements (length elements)))
  the-tree)

;; partial-tree: (listof X) natural -> (values tree (listof X))
;; Computes the partial BST representation of the n elements in elts.
;; Returns that BST, along with the elements it has not yet processed.
(define (partial-tree elts n)
  (cond [(= n 0)
         (values EMPTY-TREE elts)]
        [else
         (define left-size (quotient (- n 1) 2))
         (define-values (left-tree non-left-elts)
           (partial-tree elts left-size))
         
         (define this-entry (first non-left-elts))
         
         (define right-size (- n (+ left-size 1)))
         (define-values (right-tree remaining-elts) 
           (partial-tree (rest non-left-elts) right-size))
         
         (values (tree this-entry left-tree right-tree)
                 remaining-elts)]))

What's cool about this function is that you don't need random access to build the BST in linear time. The way the function iterates through the ordered list, keeping track of the elements it hasn't walked across yet, is just enough to do it. I dunno why I thought random access was necessary before. Good to know.