Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
(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)
(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))]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment