Lab: Binary trees

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.

Preparation

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.

Exercises

Exercise 1: Exploring the implementation

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.

Exercise 2: Sketching trees

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.

Exercise 3: Building trees

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"))

Exercise 4: Searching vectors

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?

Exercise 5: Searching trees

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?

Exercise 6: Searching binary search trees

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?

Exercise 7: Searching, revisited

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.

Exercise 8: Adding values

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

Exercise 9: Finding the largest

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

Exercise 10: A number-tree predicate

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.

For those with extra time

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

Extra 1: Alphabetically last

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

Extra 2: Counting emptiness

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.

Extra 3: Nodes vs. terminators

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?

Extra 5: Tallying tree values

Write a procedure, (count-odd ntree), that counts how many odd numbers appear in a number tree.