7 Tree Abstractions
Purpose: Build and use abstractions similar to those you have for lists, but for binary trees!
Our Tree Definition
As discussed in class recently, trees allow you to store data in a more structured way than in lists. In this lab, you will be working with full binary trees, with values present at the leaves of the tree.
; A [BinTree X] is one of ; - (make-leaf X) ; - (make-node [BinTree X] [BinTree X]) ; It represents a (full) binary tree with values (of type X) ; at the leaves of the tree (define-struct leaf [val]) (define-struct node [left right])
Exercise 1 Write the template for a BinTree X. Write at least three examples, using at least two different data types across the examples.
Exercise 2 Warm Up: Trees are similar to lists in many ways. In fact, we can easily convert from a tree into a list. Design a function tree-flatten that does just that. The leftmost value in the tree should be the first element of the list.
Given the similarities between trees and lists, it is only natural to try to extend the list functions we know and love to work on trees! In class, we saw how to write height, a function that is similar in nature to length.
; height : {X} [BinTree X] -> Natural ; Determines the height of the given tree ; This is the length of the longest path from the root to a leaf (define (height bt) (cond [(leaf? bt) 0] [(node? bt) (add1 (max (height (node-left bt)) (height (node-right bt))))]))
Exercise 3 Warm Up: Design a function tree-reverse that reverses a given tree. Reversing a tree and then flattening it should yield the same list as if the tree was flattened first, then reversed.
Tree Abstractions
Goals: Design tree abstractions, analogous to the familiar list abstractions like map.
Fairly recently, we developed the idea of list abstractions, which abstract over common patterns of recursive program design for lists. Given the parallels that have been drawn between lists and trees above, it is only natural to develop similar abstractions that work for trees!
Exercise 4 Design a function tree-map that applies a given function to all of the values in a tree to produce a new tree with the same structure but new values. Be sure to give this function the most general signature that you can!
Exercise 5 Design a function tree-andmap that takes in a predicate and determines whether all values in the tree satisfy that predicate.
Exercise 6 Design a function tree-ormap that takes in a predicate and determines whether any value in the tree satisfies that predicate.
We would like to design a tree abstraction that is analogous to filter. However, we have to make a slight change when adapting the function to work for trees. When we filter a list, we remove values that do not satisfy a predicate. What problems do we run into when we try to remove values stored at the leaves from our binary tree? To get around this issue, we can pass in an additional value that can take the place of the nodes that do not satisfy the given predicate, while still maintaining the tree’s structure. This abstraction, alongside smart choices for the base value, can still be used to solve many "filter-like" problems (especially those that occur as subproblems in more complex tree functions).
Exercise 7 Design a function, tree-filter, that takes in a predicate and replaces all values in a tree that do not satisfy that predicate with a given "base" value. (Note: unlike filter on lists, tree-filter doesn’t make the tree “smaller” exactly. Instead it acts more like a hypothetical keep-or-replace function that either keeps good values in a list or replaces them with a placeholder.)
Exercise 8 Similarly to tree-filter, we have to make another slight change to implement an abstraction analogous to foldr. Design a function tree-fold that acts like a fold over a tree. It should take in a function to apply to leaves, which is similar to foldr’s base case. It should also take in a function to combine the results of folding subtrees. These two functions should be used to compress a given tree down to a single resulting value.
Hint: Remember the “cartoon” explanation for what foldr does: it turns
into
(f A (f B (f C (f D ... base))))
Can you draw a similar cartoon for what tree-fold ought to do?
Switch pair programming roles before continuing!
The Power of Abstraction
Goals: Become comfortable using tree abstractions.
Exercise 9 Like with list abstractions, we can compose tree abstractions to easily write complicated functions. Design a function even-length-total that takes a binary tree of strings and sums the lengths of all strings with even length. (Note! Don’t use the “cheesy” solution of flattening the tree and then just working with familiar list functions. Practice working with the trees directly.)
Many of the warm-up functions that we designed can be rewritten more succinctly using tree abstractions.
Exercise 10 Re-implement the tree-flatten function using tree abstractions.
Exercise 11 Re-implement the height function using tree abstractions.
Exercise 12 Re-implement the tree-reverse function using tree abstractions.
The Universality of Fold, Part 2
Goals: Re-implement the other tree abstractions using tree-fold.
As you may have noticed when re-implementing the functions above, the tree-fold abstraction is very powerful! Similar to foldr for lists, we can implement any function that can be written following the tree template with tree-fold. To show off this power, we can even rewrite the list abstractions we implement above using tree-fold!
Exercise 13 Re-implement the tree-map function using tree-fold and no other tree abstractions.
Exercise 14 Re-implement the tree-andmap function using tree-fold and no other tree abstractions.
Exercise 15 Re-implement the tree-ormap function using tree-fold and no other tree abstractions.
Exercise 16 Re-implement the tree-filter function using tree-fold and no other tree abstractions.
As you continue utilizing trees in the future, feel free to use these tree abstractions if you find them helpful! Keep in mind that we have many variations on tree definitions (some with one or more values at the nodes, some with no values at the leaves, some with more than just leaves and nodes, etc), and each variation gets its own corresponding variant of these abstractions.
Cool Down: Often, trees are the most useful when their height is short compared to the number of leaves present. If the height of the tree is similar to the number of values present, this means that the tree has a "long branch", and its structure is more similar to that of a list. A binary tree is "balanced" when the difference in height between its left and right subtrees us at most one, and those subtrees are themselves balanced.
Exercise 17 Design a predicate balanced? that determines whether a given tree is balanced. Feel free to use as many or as few of the abstractions and other functions defined above. If you implement balanced? without using tree-fold, try re-implementing it using tree-fold to see its universality. The most simple solution may not necessarily use this abstraction.
Before you go...
If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.