Thank you to the students who showed up so that we'll have notes that that other students can read over later.

Finding This Page

• Go to http://www.cs.grinnell.edu/~rebelsky/
• Click on "CSC 151" at the top of the page
• Click on "EBoard" in the "Current" row

Overview

• About the quiz.
• Your questions.
• Sample quiz questions.
• More of your questions.

The Quiz

Topics

• Trees
• Related previous topics
  • Vectors
  • Named let
  • Pairs and pair structures

Types of questions

• Code -> Picture of Tree
• Picture of Tree -> Code
• Interpret code
  • Document
  • What is the output?
• Write code
  • Or fill in the blanks

Reminder: Key tree operations

• empty - empty tree (equiv to null)
• (empty? val) - determine if a value represents the empty tree
• (node val left right) - builds a new tree (or joins two trees with a new root value)
• (leaf val) - a special case of node in which the subtrees are empty
• (contents tree) - gets the root value (similar to car)
• (left tree) - gets the left subtree (similar to cdr)
• (right tree) - gets the right subtree (similar to cdr)

Your Questions

Trees are just vectors, right?

Yes. But we want to think about them in terms of the operations we can use, rather than the underlying representation.

What is a tree?

A tree is like a list, except two-dimensional rather than one dimensional.

Instead of one successor, each value can have two successors.

Useful for organizing some kinds of information.

Pairs are used more for lists.

With lists, we always need null on the end. Does something similar hold for trees (i.e., that there's an empty at the end)?

Yes. We assume that we'll always end a subtree with empty. A leaf has two empty subtrees.

Sample Quiz Questions

Draw a Tree

Draw the tree for the following expression. You need not draw the empty nodes.

(node 1 (node 2 (leaf 3) empty) (node 4 empty (leaf 5)))

Code a Tree

Write an expression that would generate the following tree

              4
            /   \
           /     \
         2        5
        / \      /
       /   \    /
      1     3  6

A Solution

(node 4 (node 2 (leaf 1) (leaf 3)) (node 5 (leaf 5) empty))

Code and Sketch a Tree

We might use a tree to represent reporting relationships.

• Voos reports to Kington
• Latham reports to Kington
• Kalkbrenner reports to Voos
• Walker reports to Voos
• Conner reports to Latham
• Mosenchross reports to Conner

a. Sketch a tree that shows these reporting relationships. ("reports to" can be read as "falls immediately below in the tree")

b. Write an expression to generate that tree.

Implement a Procedure - leaf

Suppose the leaf procedure were not defined. Define it.

(define leaf (lambda (val) _____))

A Solution

(define leaf (lambda (val) (node val empty empty))

Implement a procedure - tree-smallest

Implement a procedure, tree-smallest, that finds the smallest value in a non-empty tree.

(define tree-smallest
   (lambda (tree)
     (cond
       ; Leaf!
       [(and (empty? (left tree)) (empty? (right tree)))
        _________________]
       ; No left subtree
       [(empty? (left tree))
        (________ (contents tree)
                  (tree-smallest (right tree)))]
       ; No right subtree
       [(empty? (right tree))
        (________ (contents tree)
                  (tree-smallest _________))]
       ; Both left and right subtrees
       [else






        ])))

A Solution

(define tree-smallest
   (lambda (tree)
     (cond
       ; Leaf!
       [(and (empty? (left tree)) (empty? (right tree)))
        (contents tree)]
       ; No left subtree
       [(empty? (left tree))
        (min (contents tree)
             (tree-smallest (right tree)))]
       ; No right subtree
       [(empty? (right tree))
        (min (contents tree)
             (tree-smallest (left tree)))]
       ; Both left and right subtrees
       [else
        (min (tree-smallest (left tree))
             (tree-smallest (right tree))
             (contents tree))])))

Read a Procedure

What does the following procedure do?

(define tree-something
  (lambda (tree)
    (if (empty? tree)
        0
        (+ 1 (max (tree-something (left tree))
                  (tree-something (right tree)))))))

Read a Procedure

Consider the following procedure.

(define list-something
  (lambda (lst)
    (if (null? lst)
        empty
        (node (car lst) 
              (list-something (cdr lst))
              (list-something (cdr lst))))))

Sketch the output of (list-something (list 1 2 3)).

A Solution

                     (list-something '(1 2 3))

Not null

                              1
                            /   \
                           /     \
        (list-something '(2 3))  (list-something '(2 3))

We expand the left call.

                              1
                            /   \
                           /     \
                          2      (list-something '(2 3))
                         / \
                        /   \
       (list-something '(3)) (list-something '(3))

We expand the left call

                              1
                            /   \
                           /     \
                          2      (list-something '(2 3))
                         / \
                        /   \
                       3    (list-something '(3))
                      / \
                     /   \
    (list-something '()) (list-something '())

And again

                              1
                            /   \
                           /     \
                          2      (list-something '(2 3))
                         / \
                        /   \
                       3    (list-something '(3))
                      / \
                     /   \
                         (list-something '())

And again 1 / \ / \ 2 (list-something '(2 3)) / \ / \ 3 3 / \ / \ / \ / \

More Questions

What are the new things we need to know as we move from list recurstion to tree recursion?

For trees, we almost always do direct recursion. That is, recurse on the left subtree; recurse on the right subtree; grab the contents; combine.

You have to be comfortable with the "trust that the recursive call works" model.

What does tree-sum look like?

(define tree-sum
  (lambda (tree)
    ; Base case
    (if (empty? tree)
        0
    ; Recursive case
        (+ (contents tree)
           (tree-sum (left tree))
           (tree-sum (right tree))))))

That's really similar to the original list sum, isn't it?

(define list-sum
  (lambda (lst)
    ; Base case
    (if (null? lst)
        0
        ; Recursive case
        (+ (car lst)
           (list-sum (cdr lst))))))

Is it always this simple?

No. Think about tree-smallest vs list-smallest

In list smallest, there are two cases: (a) One element list or (b) more than one element list.

    (define list-smallest
      (lambda (lst)
        (if (null? (cdr lst))
            (car lst)
            (min (car lst) (list-smallest (cdr lst))))))

In tree smallest, there are four cases: (a) one element / leaf; (b) both subtrees exist; (c) no left subtree; (d) no right subtree

Each of these cases is similar, but there are more of them.