has-path.rkt

has-path.rkt

(define-struct node (k v l r))
;; BinaryTree is one of:
;; - false
;; - (make-node Natural String BinaryTree BinaryTree)
(define BT0 false)
(define BT1 (make-node 1 "a" false false))
(define BT4 (make-node 4 "d"
                       (make-node 2 "b"
                                  (make-node 1 "a" false false)
                                  (make-node 3 "c" false false))
                       (make-node 5 "e" false false)))
;; Path is one of:
;; - empty
;; (cons "L" Path)
;; (cons "R" Path)
(define P1 empty)
(define P2 (list "L"))
(define P3 (list "R"))
(define P4 (list "L" "R"))

                | false |      (make-node Nat Str BT BT)
----------------|-------|--------------------------------------
      empty     | false |                true
----------------|-------|--------------------------------------
(cons "L" Path) | false | (has-path? <left-child> (rest path))
----------------|-------|--------------------------------------
(cons "R" Path) | false | (has-path? <right-child> (rest path))

;; BinaryTree Path -> Boolean
(check-expect (has-path? false empty) false)
(check-expect (has-path? false P2) false)
(check-expect (has-path? false P3) false)
(check-expect (has-path? BT1 empty) true)
(check-expect (has-path? BT4 (list "L")) true)
(check-expect (has-path? BT4 (list "R")) true)
(check-expect (has-path? BT4 (list "L" "L")) true)
(check-expect (has-path? BT4 (list "L" "L" "R")) false)

;; has-path? bt BinaryTree p path
(define (has-path? bt p)
  (cond [(false? bt) false]
        [(empty? p) true]
        [(string=? "L" (first p))(has-path? (node-l bt) (rest p))]
        [(string=? "R" (first p))(has-path? (node-l bt) (rest p))]))