Nth Smallest Item In Binary Search Tree
February 24, 2017
We begin by writing a simple implementation of a binary search tree represented as a list of three items with the item value in the car, the left subtree in the cadr, and the right subtree in the caddr. Here are insert and member?:
(define (insert lt? x tree)
(cond ((null? tree)
(list x (list) (list)))
((lt? x (car tree))
(list (car tree) (insert lt? x (cadr tree)) (caddr tree)))
((lt? (car tree) x)
(list (car tree) (cadr tree) (insert lt? x (caddr tree))))
(else tree)))
(define (member? lt? x tree)
(cond ((null? tree) #f)
((lt? x (car tree)) (member? lt? x (cadr tree)))
((lt? (car tree) x) (member? lt? x (caddr tree)))
(else #t)))
Here’s a sample tree and a demonstration of insert and member?:
(define tree (insert < 4 (insert < 6 (insert < 0 (insert < 7 (insert < 1 (insert < 5 (insert < 2 (insert < 3 (list))))))))))
3
|
+----+--------+
| |
2 5
| |
+----+ +---+------+
| | |
1 4 7
| |
+---+ +--+
| |
0 6
> tree
(3 (2 (1 (0 () ()) ()) ()) (5 (4 () ()) (7 (6 () ()) ())))
> (do ((ns (range 9) (cdr ns))) ((null? ns))
(assert (member? < (car ns) tree) #t))
failed assertion:
(member? < (car ns) tree)
expected: #t
returned: #f
The failed assertion results from searching for 8, which is not present in the tree, so the failure is expected.
An easy solution to the exercise flattens the tree into a list, then takes the nth item in the list:
(define (enlist tree)
(cond ((null? tree) (list))
((and (null? (cadr tree)) (null? (caddr tree)))
(list (car tree)))
(else (append (enlist (cadr tree))
(list (car tree))
(enlist (caddr tree))))))
(define (nth n tree) (list-ref (enlist tree) n))
> (enlist tree)
(0 1 2 3 4 5 6 7)
> (do ((ns (range 9) (cdr ns))) ((null? ns))
(assert (nth (car ns) tree) (car ns)))
Exception in list-ref: index 8 is out of range for list (0 1 2 3 4 5 ...)
Type (debug) to enter the debugger.
Instead of a failed assertion, this function throws an error when n is out of range, which is unfriendly.
That algorithm takes quadratic time. A better solution uses depth-first search to perform an in-order traversal of the tree, counting nodes each time it visits the root of a subtree, and returning when it sees the desired item:
(define (nth n tree)
(call-with-current-continuation
(lambda (return)
(let ((n n))
(let loop ((tree tree))
(when (pair? tree)
(loop (cadr tree))
(when (zero? n)
(return (car tree)))
(set! n (- n 1))
(loop (caddr tree))))
(return #f)))))
> (do ((ns (range 9) (cdr ns))) ((null? ns))
(assert (nth (car ns) tree) (car ns)))
failed assertion:
(nth (car ns) tree)
expected: 8
returned: #f
The failed assertion is expected when n is beyond the range of the tree.
We don’t often see call-with-current-continuation, though it is a valid and important part of Scheme. Here we use call-with-current-continuation to break the depth-first recursion and return the desired node as soon as it is seen. Time complexity of the algorithm is O(n log N), where N is the unknown number of nodes in the tree and n is the requested node.
You can run the program at http://ideone.com/lrdIfu.
Programming Praxis 
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)).
(defstruct node label left right) (defun sequence-to-tree (sequence lessp) (let ((v (sort (coerce sequence 'vector) lessp))) (labels ((to-tree (min max) (cond ((> min max) nil) ((= min max) (make-node :label (aref v min))) (t (let ((mid (truncate (+ min max) 2))) (make-node :label (aref v mid) :left (to-tree min (1- mid)) :right (to-tree (1+ mid) max))))))) (to-tree 0 (1- (length v)))))) (defun nth-element (n tree) (labels ((search-nth (i node) (when (node-left node) (setf i (search-nth i (node-left node)))) (when (= i n) (return-from nth-element node)) (incf i) (when (node-right node) (setf i (search-nth i (node-right node)))) i)) (search-nth 0 tree) nil)) (loop with tree = (sequence-to-tree (loop for i below 15 collect i) (function <)) for i below 16 for e = (nth-element i tree) collect (and e (node-label e))) ;; --> (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 nil) (loop with tree = (sequence-to-tree (loop for i below 10 collect i) (function <)) for i below 16 for e = (nth-element i tree) collect (and e (node-label e))) ;; --> (0 1 2 3 4 5 6 7 8 9 nil nil nil nil nil nil)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.
(use-modules (rnrs exceptions)) ;; The value of (generator (lambda (yield) ...)) returns values as ;; many times as ... calls yield; after that it raises an exception. ;; (I have a call-with-current-continuation version somewhere. This ;; version uses delimited continuations in Guile 2.0.) (define generator (case-lambda ((proc then) (let* (($ (string #\#)) (yield (lambda args (abort-to-prompt $ args))) (k (call-with-prompt $ (lambda () (abort-to-prompt $) (proc yield) (let loop () (call-with-values (lambda () (call-with-values then yield)) loop))) values))) (lambda () (call-with-prompt $ k (lambda (k1 vs) (set! k k1) (apply values vs)))))) ((proc) (generator proc (lambda () (raise 'past)))))) ;; Search trees of strings are either empty or not empty: ;; (list) ;; (list datum lesser grater) (define this car) (define left cadr) (define rite caddr) (define (join bin val) (cond ((null? bin) (list val (list) (list))) ((string<? val (this bin)) (list (this bin) (join (left bin) val) (rite bin))) ((string<? (this bin) val) (list (this bin) (left bin) (join (rite bin) val))) (else bin))) (define (grow . data) (let loop ((bin (list)) (data data)) (if (null? data) bin (loop (join bin (car data)) (cdr data))))) (define (walk proc bin) ;; calls proc on the values in bin in inorder (if (pair? bin) (begin (walk proc (left bin)) (proc (this bin)) (walk proc (rite bin))))) (define (binth bin n) (let ((g (generator (lambda (yield) (walk yield bin))))) ;; each (g) yields the next value, so nth (g) is the result (do ((k 0 (+ k 1))) ((= k n) (g)) (g)))) (let ((bin (grow "uno" "dos" "tres" "cuattro" "cinco" "seis" "siete" "ocho"))) (define (displayln o) (display o) (newline)) (displayln "Inorder traversal:") (walk displayln bin) (displayln "Each binth:") (do ((k 0 (+ k 1))) ((= k 8)) (displayln (cons k (binth bin k)))))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.
from functools import reduce def join(tree, data): if tree is None: return (data, None, None) else: root, left, rite = tree if data < root: return (root, join(left, data), rite) elif root < data: return (root, left, join(rite, data)) else: return tree def grow(*datami): return reduce(join, datami, None) def walk(tree): '''Yield elements in inorder''' this, left, rite = tree if left: yield from walk(left) yield this if rite: yield from walk(rite) tree = grow("one", "two", "three", "four") walker = walk(tree) print(next(walker)) print(next(walker))A solution in Racket.