;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-beginner-abbr-reader.ss" "lang")((modname 14.2.2) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
(define-struct node (soc pn left right))

(define A-Tree (make-node 63 'b
                          (make-node 29 'a
                                     (make-node 15 'c 
                                                (make-node 10 'd false false)
                                                (make-node 24 'e false false))
                                     false)
                          (make-node 89 'f
                                     (make-node 77 'g false false)
                                     (make-node 95 'h
                                                false
                                                (make-node 99 'i false false)))))

(define B-Tree (make-node 63 'i
                          (make-node 29 'h 
                                     (make-node 15 'g 
                                                (make-node 10 'f false false)
                                                (make-node 24 'e false false))
                                     false)
                          (make-node 89 'd
                                     (make-node 33 'c false false)
                                     (make-node 95 'b
                                                false
                                                (make-node 99 'a false false)))))

;; Exercise 14.2.2.   Develop search-bt. The function consumes a number n and a BT. 
;; If the tree contains a node structure whose soc field is n, the function produces
;; the value of the pn field in that node. Otherwise, the function produces false. 


;; search-bt : number BT -> symbol or false
;; Use number n and a BT to compute, if the tree contains a node structure whose soc field is n,
;; the function produces the value of the pn field in that node. Otherwise, the function produces false.

; Data Definition
;  (or (empty? TB) (equal? TB false))
;  (= n (node-soc TB)) (node-pn TB)  
;   else
;     (boolean? (search-bt n (node-left TB)))
;     else (search-bt n (node-left TB))    


(define (search-bt n TB)
  (cond
    [(or
      (empty? TB)
      (equal? TB false)) false]        
    [(= n (node-soc TB)) (node-pn TB)] 
    [else
     (cond 
       [(boolean? (search-bt n (node-left TB)))
        (search-bt n (node-right TB))]     
       [else (search-bt n (node-left TB))])]))    


(equal? (search-bt 99 B-Tree) 'a)
(equal? (search-bt 29 A-Tree) 'a)
(equal? (search-bt 77 A-Tree) 'g)
(equal? (search-bt 63 A-Tree) 'b)
(equal? (search-bt 200 A-Tree) false)
(equal? (search-bt 63 B-Tree) 'i)
(equal? (search-bt 95 A-Tree) 'h)
(equal? (search-bt 15 A-Tree) 'c)