Lab 10 Binary Trees🔗

Purpose: Practice working with binary trees.

Functions on Binary Trees🔗

Consider the following definition of an abstract binary tree (think of it as a generalization of the family tree we developed in class):

(define-struct bnode [value left right])

; A [BinTree-of X] is one of

; - #false

; - (make-bnode X [BinTree-of X] [BinTree-of X])

; Interpretation: A value and left and right subtrees,

; or a sentinel value representing an empty tree

; Examples:

(define BT-0 #false)

(define BT-1 (make-bnode 10

(make-bnode 4

(make-bnode 5 #false #false)

#false)

(make-bnode 3

(make-bnode 2 #false #false)

(make-bnode 9 #false #false))))

(define BT-2 (make-bnode "College"

(make-bnode "Khoury" #false #false)

(make-bnode "Computer"

(make-bnode "of" #false #false)

(make-bnode "Sciences" #false #false))))

(define (bt-temp bt)

(...

(cond [(boolean? bt) ...]

[(bnode? bt) (... (bnode-value bt) ...

(bt-temp (bnode-left bt)) ...

(bt-temp (bnode-right bt)) ...)])))

Exercise 1 Design a function called bt-height that takes a binary tree and returns the height of the tree. (This is the length of the path to the deepest node.)

Exercise 2 Design a function called bt-flatten that takes a binary tree and returns all the values in the tree as a list. The values should be listed in left-to-right order. By this, we mean that for any given node, your resulting list should consist of first, all of the nodes in the left subtree, then the value of the node itself, then all of the nodes in the right subtree. This is what is known as a "depth-first in-order traversal." For example:

(check-expect (bt-flatten BT-2)

(list "Khoury" "College" "of" "Computer" "Sciences"))

Make sure your code produces a list in this exact order.

Exercise 3 Design a function called bt-map that takes a function and a binary tree and applies the function to each value in the tree. The function should return a new tree with the same structure as the original tree, but with the values replaced by the result of applying the function to the original. Remember to make the signature as general as possible. For example:

(check-expect (bt-map add1 BT-1)

(make-bnode 11

(make-bnode 5

(make-bnode 6 #false #false)

#false)

(make-bnode 4

(make-bnode 3 #false #false)

(make-bnode 10 #false #false))))

Exercise 4 Design a function bt-fold that acts like a fold over a tree. It should take a value which replaces the empty subtrees (think of this as the base case) and a function which combines the result of folding the left subtree, the current value, and the right subtree, in that order. The function should have the following signature:

; bt-fold : (X Y) [Y X Y -> Y] Y [BinTree-of X] -> Y

Exercise 5 Re-implement bt-height using bt-fold. Call it bt-height/v2.

Exercise 6 Reimplement bt-flatten using bt-fold. Call it bt-flatten/v2.

Exercise 7 Reimplement bt-map using bt-fold. Call it bt-map/v2.