<aside> 💡 Binary Search Trees (BSTs) consist of nodes which store data and “pointers” to other nodes (children) further down the tree. Given that BSTs are self-referential data types, functions which operate on BSTs (e.g. tree traversal)are naturally recursive.

</aside>

Defining a BST in Racket

(define-struct node (key value l r))
;; BST (Binary Search Tree) is one of:
;; - false
;; - (make-node Number String BST BST)
;; interp.
;;  - false means there is no/empty BST
;;  - key is used to look nodes up
;;  - value refers to the data held by the node
;;  - l and r are the left and right subtrees attached to the BST
;;
;; INVARIANTS:
;; - node key is > all the keys under the node's left subtree (node-l)
;; - node key is < all the keys under the node's right subtree (node-r)

(define BST0 false)
(define BST1 (make-node 1 "abc" false false))
(define BST47 (make-node 4 "dcj" false (make-node 7 "ruf" false false)))
(define BST3147 (make-node 3 "ilk" BST1 BST47))

(define sampleBST (make-node 10 "why"
                             BST3147
                             (make-node "42" "ily"
                                        (make-node "27" "wit"
                                                   (make-node "14" "olp" false false)
                                                   false)
                                        (make-node "50" "dug" false false))))

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

;; Template rules used:
;; - One of: 2 cases
;; - atomic distinct: false
;; - Compound: 4 fields (make-node Integer String BST BST)
;; - Self-reference rule: (node-l bst) and (node-r bst) are BSTs

Lookup in BSTs

• The process of looking for specific values in a BST is recursive.
  • If a node doesn’t contain a value, return false.
  • If the node contains the value you’re looking for
  • If the node’s value < the value to be found, run the lookup process on the left sub-tree.
  • If the node’s value > the value to be found, run the lookup process on the right sub-tree.

;; BST Natural -> String or false
;; Try to find node with given key, if found produce value; if not found produce false.

(check-expect (lookup-key BST0 1) false) ; base case
(check-expect (lookup-key BST1 1) "abc")

(check-expect (lookup-key BST3 0) false)
(check-expect (lookup-key BST3 7) "ruf")
(check-expect (lookup-key BST42 97) false)
(check-expect (lookup-key BST42 50) "dug")

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

(define (lookup-key t k)
  (cond [(false? t) false]
        [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)])]))