CS 101 - Lab09 Worksheet

Name:


1. Draw a picture of the binary search tree constructed by tree1.py, either on
paper or using "ASCII art" in this worksheet. Describe in a sentence or two what
it looks like.




2. What is the height of the tree?  How many leaf nodes does it have?  What does
a leaf node look like in Python?




3. What is the path from Ed to Dot, i.e., which verticies does it pass through?




4. Who is Fran's sibling in the tree?  Who is Ann's grandparent?  How many
descendants does Gail have?




5. Which of the tree1.py functions are recursive?  How does recursion simplify
these algorithms?




6. Draw a picture of the binary search tree constructed by tree2.py, either on
paper or using "ASCII art" in this worksheet. Describe in a sentence or two what
it looks like.




7. Study the tree_data function in tree2.py.  How does this algorithm traverse
the entire tree in a non-recursive way?




8. Compare the imperative paradigm of tree1.py with the object-oriented paradigm
in tree2.py.  Which version of insert() is easier to understand, and why?