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 nth 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.

Advertisements

Pages: 1 2

6 Responses to “Nth Smallest Item In Binary Search Tree”

  1. 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)
    
  2. Jussi Piitulainen said

    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:

    Inorder traversal:
    cinco
    cuattro
    dos
    ocho
    seis
    siete
    tres
    uno
    Each binth:
    (0 . cinco)
    (1 . cuattro)
    (2 . dos)
    (3 . ocho)
    (4 . seis)
    (5 . siete)
    (6 . tres)
    (7 . uno)
    
  3. programmingpraxis said

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

  4. Jussi Piitulainen said

    @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:

    (let ((tree (grow "one" "two" "three" "four")))
      (define walker (generator (lambda (out) (walk out tree)))) 
      (display (walker)) (newline)
      (display (walker)) (newline))
    
    (display "--") (newline)
    
    (let ((tree (grow "one" "two" "three" "four")))
      (define-generator (make-walker) (walk (lambda (o) (yield o)) tree))
      (define walker (make-walker))
      (display (walker)) (newline)
      (display (walker)) (newline))
    
    ;; Displays:
    ;; four
    ;; one
    ;; --
    ;; four
    ;; one
    

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

    (let ((tree (grow "one" "two" "three" "four")))
      (define-generator (make-walker) (walk yield tree))
      (define walker (make-walker))
      (display (walker)) (newline)
      (display (walker)) (newline))
    

    Nice.

  5. Jussi Piitulainen said

    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))
    
  6. r. clayton said

    A solution in Racket.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: