---
tags: labs, spr22
---

# Lab 2 (CS15): Binary (Search) Trees

### [Hey Ya!](https://www.youtube.com/watch?v=-7XnDlYY9qw)
As you listen to more 2000s songs, you keep updating your ranking as to which song is the best. One way you can conveniently store and update your ranking is to use a binary search tree!

A *binary tree* is a tree in which every node has 0, 1, or 2 children/direct subtrees. A *binary search tree* is a special kind of binary tree in which at every node, all elements with smaller values are in the left subtree and all elements with larger values are in the right subtree. A duplicate value can be in either the left or the right subtree.

In this lab, you will implement, and learn to test programs for, binary search trees.

### The Datatype

Here are two possible datatypes for a binary tree:

# version 1
data BinTree1:
  | emptytree
  | node(value :: Number, left :: BinTree1, right :: BinTree1)
end

# version 2
data BinTree2:
  | leaf(value :: Number)
  | node(value :: Number, left :: BinTree2, right :: BinTree2)
end

We saw the first type in class, and now you will work with the second type!

## Implementing Binary Search Trees with `BinTree`

At [code.pyret.org](https://code.pyret.org/), create a new file to complete your lab!

Complete the following exercise using the `BinTree2` definition (copy over only the `BinTree2` definition as the code won't compile if you have both `BinTree1` and `BinTree2` definitions in one file). Remember to use the binary tree code template that was shown in lecture.

**Task:** Write a function `tree-depth` that takes a binary tree as input and produces the height of the longest path down the tree.

**Task:** Create a set of sample trees and write a `check` block to test your `tree-depth` function.

**Task:** Write a function `has-elt` that takes a binary search tree and a number and returns a boolean indicating whether the number is in the BST.

**Task:** Develop a good set of tests for `has-elt`. The point here is to think about what combination of tree shapes and numbers cover the different cases of the algorithm. You can draw your trees on paper, indicating which numbers you would use for good `has-elt` tests. Write a short description of the situation that each tree/input is trying to test (e.g., we want to see your testing strategy, not just that you came up with some collection of examples.)

**Task:** Try to write a function `add-elt` that takes a binary search tree (with the structure of `BinTree2`) and a number as input and produces a new binary search tree. The new tree should have all the same elements as the original, as well as the given number. You should move on to the next task after about **ten minutes.**

:::spoiler Click if you're really stuck

How did we add an element to our `BinTree1`-style trees in lecture? How can we try to do something similar with `BinTree2`? What do we have to do differently? Are we somehow limited by this new `BinTree2`?
:::
<br>

::: spoiler Click if you're really *really* stuck

Although `BinTree1` and `BinTree2` are fairly similar, the key difference that makes the `add-elt` function for `BinTree2` so difficult is the fact that leaves have their own value. For instance, take this example of a `BinTree2` tree (also drawn out below):

`node(4, node(1, leaf(0), leaf(3)), leaf(5))`

If we were to insert a new value, say `2`, how would we do this? You can imagine the following steps:

1. `2` is less than `4`, so travel to its left branch
2. `2` is greater than `1` so travel to its right branch
3. `2` is greater than `0`, so turn `leaf(0)` into a `node(0, __, __)` and place a `leaf(2)` into its right branch to get `node(0, __, leaf(2))`

But now, we are left wondering what to put into the left branch of our current node. Because of our `BinTree2` definition, our only options are a `node` or a `leaf`, and neither seem to be appropriate here. *This is the problem!* We do not encounter this when we choose to use the `BinTree1` implementation where a leaf does not contain a value for the tree.

If you are still confused, feel free to call over a TA.
:::
<br>

**Task:** Discuss how you would modify either the `BinTree2` datatype or the assumptions on the `add-elt` function so that you could successfully add an element to `BinTree2`. What are the upsides and downsides to these ideas?

What do you notice about the code from lecture vs the code you wrote? Which version do you prefer and why?

:::success
**Checkpoint:** Tell your TA what you came up with for the questions, and have a TA check your work!
:::

### Runtime

Refer to the [guide to doing run-time annotations](https://hackmd.io/RR1Bkq1LQtirSZl_OLwpew) as needed.

Your functions will metaphorically ["walk a thousand miles," and "I need you"](https://youtu.be/Cwkej79U3ek) to figure out how long this will take!

**Task:** Look at this annotated `add-elt` from class. The annotations have some errors. Find and fix the errors.

fun add-elt(bst :: BinTree1, val :: Number) -> BinTree1:
  doc: "adds val to bst, obeying Binary Search Tree rules"
  cases(BinTree1) bst: # 1 access
    | empty => node(val, emptytree, emptytree)  # 1 comparison, 3 accesses, 1 instantiation
    | node(v, l-tree, r-tree) => # 1 comparison
      if val == v:    # 2 accesses
        bst
      else if val < v: # 2 accesses
        add-elt(l-tree, val) # T-add-elt(N / 2), 2 accesses
      else:
        add-elt(r-tree, val) # T-add-elt(N / 2), 2 accesses
      end
  end
end
# Total: T-add-elt(N) = 1 + 5 + 1 + 2 + 2 + T-add-elt(N/2) + 2

Now, you will plot some runtimes over different intervals and discuss the implications.

**Task:** copy the entirety of the following code to a new Pyret file:

:::info
You do not have to understand this code, but it is commented if you are curious!
:::

:::spoiler **Code to copy**

include math
include plot
include tables
import color as C

color-list = [list: C.peru, C.deep-sky-blue, C.sea-green, C.yellow, C.dark-blue]

fun graph-big-o(max-x :: Number, runtime-funs :: List<(Number -> Number)>) -> Image:
  # for every function in runtime-funs, match it to a color and create a
  # function-plot
  plots-list = map2(lam(f, c): function-plot(f, _.{color: c}) end,
    runtime-funs,
    # make sure we match the length of color_list to the length of runtime-funs
    color-list.take(runtime-funs.length()))
  
  # find the maximum value of y over all of the functions
  all-max = max(runtime-funs.map(lam(f): f(max-x) end))
  
  # display the plots of all of the functions
  display-multi-plot(
    plots-list,
    _.{
      title: 'runtime of all functions',
      x-min: 0,
      x-max: max-x,
      y-min: 0,
      y-max: all-max
    })
end

:::
<br>

You can now graph the runtime of up to 5 functions simultaneously! For example, to compare the runtime of `2*N + 1` to `N + 20` for an input size up to `N=30`, you could run

graph-big-o(30, [list: lam(n): (2 * n) + 1 end, lam(n): n + 20 end])

You can also define recurrence relations in the Pyret file, and plot them. Copy the following relation into the file:

fun rec-log(n :: Number) -> Number:
  if n <= 1:
    40 # base case
  else:
    40 + rec-log(n / 2) # recurrence
  end
end

Now you can use this function as an argument to `graph-big-o`: `graph-big-o(20, [list: rec-log])`. What do you notice about the "smoothness" of this graph, as opposed to the others? Why do you think this is?

**Task:** Compare the runtime of three functions: logarithmic, linear, and quadratic. Run:

graph-big-o(10, [list: rec-log, lam(n): (4 * n) + 60 end, lam(n): n * (n - 2) end])

and try increasing the value of the 1st input until you find the points at which the different runtimes overtake each other. What do you notice?

:::success
**Checkpoint:** Show a TA what you came up with!
:::

### Contrasting to Java

The following Java classes correspond to `BinTree1`:

interface IBinTree {}

class EmptyTree implements IBinTree {}

class Node implements IBinTree {
  int val;
  IBinTree left; 
  IBinTree right; 
}

A more conventional Java binary tree class might look like:

class BinTree {
  int val;
  BinTree left;  // use null when out of tree
  BinTree right; // use null when out of tree
}

**Task:** Contrast these two approaches to Java classes. If you were to implement `addElt` as a method in each, how would the code differ between the two? What do you see as the benefits and tradeoffs of each?

*Part of the punchline here is that the datatypes we get from functional programming are pure object-oriented: they don't allow a null-based implementation, which is not pure object-oriented (because in pure OO, code never asks "what type of data is this"). A takeaway here is that datatype-based functional programming is strongly related to OO programming from a class-structure perspective.*

## [U + Me = Us](https://www.youtube.com/watch?v=pMWxnjgvUQM): Design practice with expression trees

Consider an expression like `(4 + 5) * (7 - 2)`. Programs *interpret* this expression by splitting it into subexpressions, as follows:


**Task:** Design a datatype that represents mathematical expressions, i.e.

data Expression:
    | ...
end

**Task:** Create each of the following expressions using your datatype and constructors:

- `5`
- `3 + 2 + 4`
- `(4 + 5) * (7 - 2)`
- `6 - (-4 * (8 - 2))`

**Task:** If you have time, write a function `calc` that takes an Expression and returns a number (being the result of that computation).

fun calc(expr :: Expression) -> Number:
  cases (Expression) expr:
   | ...
  end
end

::: info
*Note*: This is a taste of how languages work under the hood: programming tools convert your program into trees like this, and use programs like `calc` to run your programs.
:::

:::success
**Checkoff!** Congratulations! Once a TA signs off on your work, you've completed this week's lab. Nice job!
:::
______________________________

*Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the [anonymous feedback form](https://forms.gle/JipS5Y32eRUdZcSZ6).*