Laboratory: Binary Trees

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 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 those 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

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.

a. Sketch the following trees.

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. The (visualize-tree tree width height) procedure creates a sketch of a tree in an image of the specified width and height. Using a width and height of 200, check your answers from part a. For example, you might write the following instruction.

> (visualize-tree (node 0 (leaf 1) (leaf 2)) 200 200)

Exercise 3: Adding values

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 4: Finding the largest

Write a procedure, (number-tree-largest tree), that finds the largest value in a number tree. Follow the pattern for recursion over a tree.

> (number-tree-largest empty)
error!
> (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 5: 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: 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 2: 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 3: Tallying Values

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