Binary Search Tree - lookup and path (in racket)

bst-lookup-path.rkt

#lang htdp/bsl

;
; Invariants
; ----------
; at each level:
;  - all accounts in left sub-tree have account number
;    less than root;
;  - all accounts in right sub-tree have account number
;    greater than root;
;

;
; PROBLEM:
;
; Design a data definition to represent binary search trees.
;

(define-struct node (key val l r))
;; BST (Bianry Search Tree) is one of:
;;  - #false (base case)
;;  - (make-node Integer String BST BST) (self-reference)
;; Interp: #false means no BST, or empty BST
;;         - key is the node's key
;;         - val is the node's value
;;         - l is left sub-tree
;;         - r is right sub-tree
;;
;; INVARIANT
;; ---------
;; for a given node:
;;    - key is > than all keys in its l(eft) child
;;    - key is < than all keys in its r(ight) child
;;    - the same key never appears more than once in the tree
(define BST0 #false)

(define BST1 (make-node 1 "abc" #f #f))

(define BST4 (make-node 4 "dcj" #f (make-node 7 "ruf" #f #f)))

(define BST3 (make-node 3 "ilk" BST1 BST4))

(define BST42
  (make-node 42 "ily"
             (make-node 27 "wit" (make-node 14 "olp" #f #f) #f)
             (make-node 50 "dug" #f #f)))

(define BST10
  (make-node 10 "why" BST3 BST42))

#;
(define (fn-for-bst t)
  (cond [(false? t) (...)]
        [else
         (... (node-key t)                  ; Integer
              (node-val t)                  ; String
              (fn-for-bst (node-l t))       ; BST
              (fn-for-bst (node-r t)))]))   ; BST

;; Template rules used
;;  - one of: 2 cases
;;  - atomic distinct: #false
;;  - compound: (make-node Integer String BST BST)
;;  - self-reference: (node-l t) has type BST
;;  - self-reference: (node-r t) has type BST


;; =============================================================================
;; FUNCTIONS

;
; Complete the design of the lookup-key function below. Note that
; because this is a search function it will sometimes 'fail'. This
; happens if it is called with an key that does not exist in the BST it
; is provided. If this happens the function should produce #false. The
; signature for such a function is written in a special way as shown
; below.
;

;; BST Natural -> String or #false
;; Try to find a node with given key. If found produce
;; value; if not found produce #false.
(check-expect (lookup-key BST0  99) #f)
(check-expect (lookup-key BST1   1) "abc")
(check-expect (lookup-key BST1   0) #f)    ; L fail
(check-expect (lookup-key BST1  99) #f)    ; R fail
(check-expect (lookup-key BST10  1) "abc") ; L L succeed
(check-expect (lookup-key BST10  4) "dcj") ; L R succeed
(check-expect (lookup-key BST10 27) "wit") ; R L succeed
(check-expect (lookup-key BST10 50) "dug") ; R R succeed

;(define (lookup-key t k) "") ;stub

;<template according to BST, and an additional atomic parameter k>
(define (lookup-key t k)
  (cond [(false? t) #f]
        [else
         (cond [(= k (node-key t)) (node-val t)]
               [(< k (node-key t)) (lookup-key (node-l t) k)]
               [(> k (node-key t)) (lookup-key (node-r t) k)])]))

;; BST Integer -> ListOfString
;; Produce path of search for key in BST; pat is
;; list of "L"|"R", ends with "Succeed"|"Fail".
(check-expect (path #f        0) (list "Fail"))
(check-expect (path BST42    99) (list "R" "R" "Fail"))
(check-expect (path BST3     -1) (list "L" "L" "Fail"))
(check-expect (path BST10    10) (list "Succeed"))
(check-expect (path BST10     3) (list "L" "Succeed"))
(check-expect (path BST10    42) (list "R" "Succeed"))
(check-expect (path BST10     4) (list "L" "R" "Succeed"))
(check-expect (path BST10    27) (list "R" "L" "Succeed"))
(check-expect (path BST10     1) (list "L" "L" "Succeed"))
(check-expect (path BST3      7) (list "R" "R" "Succeed"))

;(define (path t k) "") ;stub

(define (path t k)
  (cond [(false? t) (list "Fail")]
        [else
         (cond [(= k (node-key t)) (list "Succeed")]
               [(< k (node-key t)) (cons "L" (path (node-l t) k))]
               [(> k (node-key t)) (cons "R" (path (node-r t) k))])]))