<style> h3 { border-bottom: 1px solid #ccc; } section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; background-color: #f7f7f7; border: 1px solid #ccc; } summary { font-weight: bolder; } summary:hover { text-decoration: underline; } .todo { color: #ff00ff; border: 2px dashed #ff00ff; padding: 0em 1em; border-radius: 5px; //display: none; // UNCOMMENT TO HIDE TODOs } </style> # Lab 2 (CS15): BSTs and other trees (Spring 2025) **The goals of this lab are to:** - Work with Binary Search Trees - Compare and contrast representations of Binary Search Trees - Plot and compare different runtime functions - Understand and work with Object-Oriented definitions of tree-like data structures ## Getting Starter Files with GitHub You can clone the starter files for this lab at this **[GitHub Classroom link](https://classroom.github.com/a/CAYbmJpu)**.  **[Look here for instructions](https://docs.cs200.io/s/java-stencil-setup-guide#Accepting-an-Assignment-on-GitHub-Classroom)** on how to accept the assignment and open the code in IntelliJ. Refer to the [GitHub guide](https://docs.cs200.io/s/github-guide) if you are unfamiliar with it. Make sure you push your code regularly to save progress! ## Binary search trees A _binary tree_ is a tree in which every node has 0, 1, or 2 children/direct subtrees. A _binary search tree_ (BST) 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, and every subtree is itself a BST. A duplicate value can be in either the left or the right subtree, though we often work with BSTs that do not have duplicate values. In this lab, you will implement, and learn to test programs for, BSTs. In the src folder of the starter code, a BST is represented with two classes. `NodeTree` holds a value and two tree children, while `EmptyTree` simply represents an empty tree. (These are similar to the definitions that we saw in lecture on Monday, except here the EmptyTree has no data, unlike the InitRound example which did – you can think about the reason for this change after you work with the example). :::info <details> <summary> <b><i>Note:</i></b> Broad Overview of Starter Code </summary> ```java public interface IBST { ... } public class EmptyTree implements IBST { public EmptyTree() { } // ...methods that implement IBST } public class NodeTree implements IBST { private String val; private IBST left; private IBST right; public NodeTree(String val, IBST left, IBST right) { this.val = val; this.left = left; this.right = right; } // ...methods that implement IBST } ``` </details> ::: :::warning Note that there is nothing in the definition of  `IBST` that enforces the rule that all smaller elements are in the left subtree and all larger elements are in the right subtree. This enforcement will be up to you as you write the methods below. ::: **Task 1:** In the provided `BSTTest.java` file, we’ve created one example binary search tree. Draw (on paper or in a note app) three examples of BSTs (including at least one with “height” larger than 3; the _height_ or _depth_ is the number of nodes in the longest path from the top of the tree down to a leaf).  Add them to the `BSTTest.java` file by declaring them in the same way that `t1` is declared and initializing them in the setup method. **Task 2:** Write tests for and implement a method called `sumBST` which returns the sum total of all of the values in the tree, as an int. You will need to modify `BSTTest.java`, `IBST.java`, `NodeTree.java`, and `EmptyTree.java`. This means adding a method header (in `IBST.java`), a method for an empty tree (in `EmptyTree.java`), and a method for a non-empty tree (in `NodeTree.java`) as well as a comprehensive set of tests (in `BSTTest.java`). **Task 3a:**  On paper or a note-taking program, determine the _depths_ of the trees you drew in Task 1 (the definition of _depth_ is in task 1). Identify the relationship between the depth of a tree and depths of its left and right children. (This is like what we have been doing for examples of recursive functions on lists, but you can do this on paper, rather than by writing the examples as JUnit assertions.) :::success **Checkpoint:** Have a TA check your work! ::: **Task 3b:** Write tests for and implement a method called `depthBST` which returns the depth of a BST. You will need to modify `BSTTest.java`, `IBST.java`, `NodeTree.java`, and `EmptyTree.java` in a similar fashion as you did in Task 2. **Task 4:** Write tests for and implement a method called `hasElt`  which takes an `int` value and returns true if the value is in the BST and false otherwise. **You should make this code as efficient as you can – do not go down subtrees where you know the value won’t exist.** You will need to modify `BSTTest.java`, `IBST.java`, `NodeTree.java`, and `EmptyTree.java`. :::warning ***Note:*** if you have less than one hour left in lab, skip task 5 and move on to Task 6 so that you get some practice with runtime as part of lab. ::: **Task 5:** Write tests for and implement a method called `addElt` which takes an int value and returns a new BST with the value added to the BST, preserving the binary search tree definition. :::info <details> <summary> <b><i>Note:</i></b> Pointers and Tips </summary> You can assume that all elements in the BST are unique – if the BST contains the value to be added, you should just return the tree unchanged. You will need to modify `BSTTest.java`, `IBST.java`, `NodeTree.java` and `EmptyTree.java`.  As you write your tests, try to think about how you could use other methods that you’ve already written in lab to help test `addElt`, rather than necessarily testing for the exact arrangement of numbers in nodes. Can you write a meaningful test using `sumBST` for example? Is `hasElt` useful? Good tests can check for things other than structure. </details> ::: :::success ***Checkpoint***: Have a TA check your work! ::: ## Runtime Refer to the [guide for doing run-time annotations](https://docs.cs200.io/runtime) as needed. **Task 6:** Look at the following approach to the shopping cart problem from homework 1A.  Someone has started to annotate the lines of code with operation counts for run time. The annotations have some errors. Find and fix the errors. How does this runtime compare to the other version (using map/filter) that we went over in class? (The annotations put the cost just above the bit of code that incurred the cost, as we did in the lecture notes from Friday.) ```java= public double checkout1(FuncList<Item> cart) { // process the cart items // 1 + 1 + 1 (get cart, call map, call sum) double cartTotal = cart.map(Item::cost).sum(); double shoeCost = // 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 cart.filter(i -> i.name().equals("shoes")).map(Item::cost).sum(); // 1 + 1 + 1 + 1 + 1 + 1 + 1 int numHats = cart.filter(i -> i.name().equals("hat")).size(); // compute discounts – the "? then :" form is a one-line if/else expression. // i.e. if numHats >= 2, then hatDiscount = 10. Otherwise hatDiscount = 0 // 1 + 1 + max(0, 0) double hatDiscount = (numHats >= 2) ? 10 : 0; // 1 + 1 + max( 0, 0) double shoeDiscount = (shoeCost >= 100) ? shoeCost * 0.2 : shoeCost; // apply the discounts // 1 + 1 + 1 + 1 + 1 return cartTotal - hatDiscount - shoeDiscount; } // Tco1 = 3 + 8 + 7 + 2 + 2 + 5 = O(N) where N is the number of elements ``` :::danger **Write down one thing you see as an important takeaway from annotating this example.** ::: Now, you will plot some runtimes over different intervals and discuss the implications. **Task 7:** [Open this link](https://code.pyret.org/editor#share=1WWDH-L9uEnLUfZmg57APYjFgNlOOx4UU\&v=6d122f0) and press the blue Run button at the top-right corner of the screen (for now, nothing should be output). Copy the following command into the prompt on the right window (the >>>) and press enter.  graph-big-o(10, [list: rec-log, lam(n): (4 * n) + 60 end, lam(n): n * (n - 2) end]) You should see a graph appear that plots three recurrence relations (runtime formulas):  - _T1(n) = 40 + T1(n/2)_ (defined as rec-log in the left window)  - _T2(n) = 4 \* n + 60    (defined as_ `lam(n): (4 * n) + 60 end` _in the list)_  - _T3(n) = n \* (n -2)      (defined as_ `lam(n): n * (n - 2) end` _in the list)_  The first argument to `graph-big-o `(here 10) indicates which inputs (0 … 10) are plotted for each function in the list (in second argument to `graph-big-o`). What do you notice about the “smoothness” of the `rec-log` plot, as opposed to the others? Why do you think this is? **Task 8:** Task 7 had you plot 3 functions: logarithmic, linear, and quadratic. Run the command again and change the first input to `graph-big-o` (initially, 10), which represents N. Vary the value of N until you find the points at which the different runtimes overtake each other. What do you notice? :::info <details> <summary><b><i>Note:</i></b> More about the Plotting Tool</summary> If you ever want to come back to this plotting tool, you can! The command above takes in a list of runtimes, so you can provide even more functions to plot by copying the syntax. You can also define more recurrences on the left side of the window, following how rec-log is defined, and pass them in as arguments as well. </details> ::: :::success ***Checkpoint***: Have a TA check your work! ::: ## OO-style design for expression trees Now let’s try to build on the OO-style class definitions from above for a design problem. Consider an expression like `(4 + 5) * (7 - 2).` Programs _interpret_ this expression by splitting it into subexpressions, like this:  **Task 9:** Design some class(es) that represent mathematical expressions. You can do this task on paper, in a note taking application, or in IntelliJ. You should start with defining an interface called `IExpression`. All of your class(es) should implement `IExpression`.  Think about how operators and values can be represented in a tree. **Task 10:** Create variables of type `IExpression` and initialize them to represent the following expressions using your class(es): * `5` * `3 + 2 + 4` * `(4 + 5) * (7 - 2)` * `6 - (-4 * (8 - 2))` **Task 11:** If you have time, add a method called `calc` to `IExpression` that returns the result of the computation as an `int`. Implement the method in each of the classes you defined. :::info ***Note:*** This is a taste of how languages work under the hood: programming tools convert your program into trees like this, and use methods like `calc` to run your programs. ::: :::success ***Checkpoint***: Have a TA check your work! ::: ## Design Challenge: Numbers in Leaves? (Optional) Here is an alternative way of implementing BSTs in an object-oriented style:  ```java public interface IBST2 { ... } public class Leaf implements IBST2 { private String val; public Leaf(String val) { this.val = val; } // ... } public class NodeTree2 implements IBST2 { private String val; private IBST2 left; private IBST2 right; public NodeTree2(String val, IBST2 left, IBST2 right) { this.val = val; this.left = left; this.right = right; } // ... } ``` Originally, we defined a tree with one node as:  IBST originalLeaf = new NodeTree(“a”, new EmptyTree(), new EmptyTree()); This same tree would be represented in the alternative way as: IBST2 alternativeLeaf = new Leaf(“a”); **Task 12:** On paper or in a note taking program, contrast how you would instantiate the following tree using the original way, and the alternative way:  **Task 13:** Now try to do the same for the following tree. What do you notice? What do you see as the benefits and drawbacks of each approach? Try to come up with at least one argument for using each way.  *** _Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS0200 document by filling out the_ [_anonymous feedback form_](https://forms.gle/Kpk1Do76jF2eVSUP8)_._