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

;; (empty? BT) produce false (do not compare)
;; (and (left BT) (right BT)) compare right and left nodes and produce two recursivities 
;; (left BT only) compare left node and produce recursivity
;; (right only) compare right node and produce recursivity
;; else compare and stop the recursivity

(define (search-bt n a-bt)
  (cond
    [(empty? a-bt) false]
    
    [(and
      (not (equal? (node-left a-bt) false))
      (not (equal? (node-right a-bt) false)))
     (cond
       [(equal? n (node-soc a-bt)) (node-pn a-bt)]
       [(boolean? (search-bt n (node-left a-bt)))
        (search-bt n (node-right a-bt))]
       [else (search-bt n (node-left a-bt))])]
    
    [(not (equal? (node-left a-bt) false))
     (cond
       [(equal? n (node-soc a-bt)) (node-pn a-bt)]
       [else (search-bt n (node-left a-bt))])]
    
    [(not (equal? (node-right a-bt) false))
     (cond
       [(equal? n (node-soc a-bt)) (node-pn a-bt)]
       [else (search-bt n (node-right a-bt))])]
    
    [else 
     (cond
       [(equal? n (node-soc a-bt)) (node-pn a-bt)]
       [else false])]))



(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)