Problem Set 9
Here is a data definition for a binary tree of numbers:
;; A BTN is one of |
;; - Number |
;; - (make-node BTN BTN) |
(define-struct node (left right)) |
Problem 1 Design a function, btn-height, that takes in a binary tree of numbers and computes the maximum distance from the root to any leaf. Here "distance" is measured by adding 1 for each internal node on the way from the root to the leaf.
Here are some examples (you should develop more to fully test your code):
(check-expect (btn-height 42) 0) |
(check-expect (btn-height (make-node 2 (make-node 4 9)) 2)) |
Problem 2 Design a function, btn-sum, that takes in a binary tree of numbers and computes the sum of all leaves.
(check-expect (btn-sum 42) 42) |
(check-expect (btn-sum (make-node 2 (make-node 4 9)) 15)) |
Problem 3
A leafy binary tree is a binary tree with the symbol 'leaf at its leafs (as opposed to, say, a number).
Design a function that consumes a natural number n and creates (a list of) all the leafy binary trees that have height n.
Hint: Design a function that consumes a natural number n, and creates (a list of) all leafy binary trees of height equal or less than n.
Hint: If you have to use filter to remove things from the list, you’re working too hard.
Hint: It might be helpful to draw pictures.
Note: this is not about abstraction; it’s a kind of puzzle that will exercise your ability to think recursively. (We hope you) Have fun...