CISC108 Lecture Notes - Lecture 15: Binary Search Tree, Social Security Number, Binary Tree

• School: University of Delaware
• Department: Computer and Information Sciences
• Course: CISC108
• Professor: Siegel Stephen

Document Summary

; bt right : second relation (define-struct node (social name left right)) ; template for function consuming a bt: (define (bt-fun bt) (cond. ; define some examples and draw them (upside down) (define bt1 (make-node 2 steve (make-node 17 brandon (make-node 33 bill #false #false) #false) (make-node 5 hope #false #false))) (define bt2 (make-node 33 el #false #false)) The function consumes a number and a bt and determines. ; whether the number occurs as a social security number of a node in the tree. ;; number number : social security # to search for. ;; produces: #true iff the tree rooted at bt contains a node. ;; with the given number (check-expect (contains-bt 33 bt1) #true) (check-expect (contains-bt 1 bt1) #false) (define (contains-bt number bt) (cond. [(node? bt) (or (= number (node-social bt)) (contains-bt number (node-left bt)) (contains-bt number (node-right bt)))])) The function consumes a number n and a bt.