- Assigned
- Monday, Nov 12, 2018
- Due
- Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
- Summary
- In this laboratory, you will further explore issues of recursion over trees introduced in the reading on pairs and pair structures and continued in the reading on trees.

a. Make sure that you have the reading on trees open in a separate tab or window.

Recall that the pattern for recursion over a tree usually requires *two* recursive calls: one for the left subtree and one for the right subtre.

```
(define tree-proc
(lambda (tree)
(if (empty? tree)
(base-case other)
(combine (contents tree)
(tree-proc (left tree))
(tree-proc (right tree))))))
```

b. Make sure that you have a piece of paper and writing instrument handy.

c. Make a copy of ** binary-tree-lab.rkt**, which contains the code for this lab.

a. The implementation of `node`

, `left`

, `right`

, and `contents`

in
`tree-lab.rkt`

are different than the vector implementations in the
corresponding reading. Identify and explain
the differences.

b. Determine what happens when we call `contents`

, `left`

, and `right`

on values that are not nodes.

c. `tree-lab.rkt`

contains two relatively basic procedures that are not
mentioned in the reading: `leaf`

and `leaf?`

. Read the code for those
two procedures and determine what they do.

As is the case with lists, we can look at trees through Scheme expressions and through diagrams. Let’s consider both.

a. What Scheme values do you expect to see when you enter each of the following expressions?

`empty`

`(leaf 0)`

`(node 0 (leaf 1) (leaf 2))`

`(node 0 (node 1 (leaf 2) empty) (leaf 3))`

`(node 0 (node 1 empty (leaf 2)) (leaf 3))`

`(node 0 (node 1 (leaf 2) (leaf 3)) (node 6 empty (node 7 (leaf 8) empty)))`

b. Check your answer experimentally.

c. The reading provides a simple way to sketch binary trees. For a node, we write the value in the node and draw arrows to the subtrees. For the empty tree, we just draw a simple sign.

d. Sketch the trees from part a.

The code for this lab contains a procedure, `vector->tree`

.

a. Read the documentation for the procedure and suggest why you think we’ve included it in the sample code.

b. Predict what results you will get for each of the following expressions.

`(vector->tree (vector))`

`(vector->tree (vector "a"))`

`(vector->tree (vector "a" "b"))`

`(vector->tree (vector "a" "b" "c"))`

`(vector->tree (vector "a" "b" "c" "d" "e"))`

`(vector->tree (vector "a" "b" "c" "d" "e" "f" "g"))`

The reading contains two procedures for searching trees. Before we start searching trees, let’s remind ourselves of how we might search vectors.

a. Add the following procedure to your definitions pane.

```
(define vector-find
(lambda (vec str)
(let kernel ([pos (- (vector-length vec) 1)])
(if (< pos 0)
#f
(let ([current (vector-ref vec pos)])
(if (string-ci=? str current)
current
(kernel (- pos 1))))))))
```

b. Explain, in your own words, how this procedure works.

c. Create the following vector.

```
(define names (vector "Anh Thu" "Charlie" "Ella" "Hongyuan" "Jemuel" "Marli"
"Ritika" "Samuel" "Sarah" "Titus" "Zachary" "Zander"))
```

d. What names do you expect the `vector-find`

to look at when searching
for `"sarah"`

?

e. Check your answer experimentally (e.g., by putting a breakpoint in
the body of the let and inspecting the value of `current`

).

f. If the vector contains 1000 elements, how many values do you expect to look at when searching for an element not in the vector?

a. The reading and lab provide two different procedures for searching trees. What are they? How are they similar? How are they different?

b. Convert the `names`

vector from the prior exercise into a tree.

```
; A tree of names
(define ton (vector->tree names))
```

c. Sketch that tree on a piece of paper.

d. What names do you expect the `tree-contains?`

to look at when searching
for `"sarah"`

?

e. Check your answer experimentally (e.g., by putting a breakpoint at
the start of the body of `tree-contains?`

and inspecting the value of
`tree`

at each recursive call).

f. What names do you expect the `tree-contains?`

to look at when searching
for `"Sarah"`

?

g. Check your answer experimentally (e.g., by putting a breakpoint at
the start of the body of `tree-contains?`

and inspecting the value of
`tree`

at each recursive call).

h. If the vector contains 1000 elements, how many values do you expect to look at when searching for an element not in the vector?

a. What names do you expect the `bst-find`

to look at when searching
for `"Sarah"`

?

b. Check your answer experimentally (e.g., by putting a breakpoint at
the start of the body of `bst-find`

and inspecting the value of
`bst`

at each recursive call).

c. What names do you expect the `bst-find`

to look at when searching
for `"sarah"`

?

d. Check your answer experimentally (e.g., by putting a breakpoint at
the start of the body of `bst-find`

and inspecting the value of
`bst`

at each recursive call).

e. If the vector contains 1000 elements, how many values do you expect to look at when searching for an element not in the vector?

Let’s search another vector, this time of science disciplines.

a. Create the tree `sciences`

using the following command.

```
(define sciences
(vector->tree (vector "Mathematics" "Statistics" "Computer Science"
"Physics" "Chemistry" "Biological Chemistry"
"Biology" "Psychology")))
```

b. What values do you expect `bst-find`

to consider as it looks for
`"psychology"`

?

c. Check your answer experimentally.

d. What values do you expect `bst-find`

to consider as it looks for
`"computer science"`

?

e. Check your answer experimentally.

f. If your experimental results did not match your predicted results, explain why.

You’ve been using some tree procedures. It’s time to start writing a few
of your own. Write a procedure, `(number-tree-sum tree)`

that sums the values in a number tree. You should follow the pattern
for recursion over a tree.

```
> (number-tree-sum empty)
0
> (number-tree-sum (leaf 5))
5
> (number-tree-sum (node 5 (leaf 2) empty))
7
> (number-tree-sum (node 5 empty (leaf 3)))
8
> (number-tree-sum (node 5 (leaf 3) (leaf 4)))
12
> (number-tree-sum (node 5 (node 2 (leaf 3) empty) (node 10 empty (leaf 1))))
21
```

Write a procedure, `(number-tree-largest tree)`

, that finds the largest value in a number tree.

The recursion for this problem is potentially difficult in that you may need to consider four cases for non-empty trees: (1) both the left and right subtree are empty (that is, you are at a leaf); (2) the left subtree is empty and the right is not; (3) the right subtree is empty and the left is not; (4) both subtrees are nonempty.

```
> (number-tree-largest empty)
error!
> (number-tree-largest (leaf 5))
5
> (number-tree-largest (leaf -5))
-5
> (number-tree-largest (node 5 (leaf 2) empty))
5
> (number-tree-largest (node 5 empty (leaf 8)))
8
> (number-tree-largest (node 5 (leaf 9) (leaf 8)))
9
> (number-tree-largest (node 3 (leaf 4) (leaf 5)))
5
> (number-tree-largest (node 8 (leaf 7) (leaf 6)))
8
> (number-tree-largest (node 5 (node 2 (leaf 3) empty) (node 10 empty (leaf 1))))
10
```

As you may recall from the reading, a number tree is a tree that contains only numbers. That is,

- The empty tree is a number tree.
- If
`t1`

and`t2`

are number trees and`num`

is a number, then`(node num`

`t1`

`t2`

) is a number tree. - Nothing else is a number tree.

Using this recursive definition, write a procedure, `(number-tree? val)`

that returns true (`#t`

) if *val* is a number tree and false (`#f`

)
otherwise.

If you find that you have extra time, you might want to attempt one or more of the following problems.

Write a procedure, `alphabetically-last`

, that takes a nonempty tree of
strings as input and finds the alphabetically last string in the tree.

At the tip of every part of the tree is the special `empty`

symbol. Write
a procedure that counts how many times `empty`

appears at the fringe of
a tree.

As you may recall, a tree is either (a) empty or (b) a node that contains a value and two other trees. In the reading, you saw a procedure that counted the number of values in a tree. In this lab, you wrote a procedure that counted the number of empty symbols in a tree. What is the relationship between the numbers returned by those two procedures?

Write a procedure, `(count-odd ntree)`

, that counts how many odd numbers
appear in a number tree.