# **Lab 9: Data Structures and Recursion**

:::warning
<b>Dates: Tuesday, November 12 - Thursday, November 14</b>
:::

# Lab Overview

In this lab, you will get hands-on practice with recursion using a very naturally recursive data structure - binary trees. Both this data structure and recursion will be a big focus in CSCI0200, so having a good grasp of them now will only help you down the road if you continue with CS@Brown. Before you get started, you might want to review the lecture slides about [Binary Trees]() and [Recursion](https://cs.brown.edu/courses/cs015/lecture/pdf/CS15.Lecture_16_Recursion.10.29.24.pdf). As always, if you have any questions, call us over, and we will lend you a hand!

The slides for this section (a very helpful reference) are linked [here.](https://docs.google.com/presentation/d/1BVieiVG20E25o-IHiL51joDj5weXNIkdtWpOzuLYhHE/edit?usp=sharing)

## Goals

1. Understand the recursive structure of a Binary Tree
2. Practice tracing out recursion through summing a Binary Tree
3. Write recursive methods to traverse and search a Binary Tree

## Silly Premise
Aang is hanging out with the past Avatars, and he wants a way to line them all up for a group photo. He wants to be in the front, with the past two Avatars, Roku and Kyoshi, behind him, and two more Avatars behind each of them, and so on and so on. He suddenly realizes that this arrangement reminds him of a data structure: binary trees! In this lab, you'll learn how to make and traverse your own binary tree!

# Binary Trees
Click [here](https://classroom.github.com/a/Gwn3LlPc) to get the stencil from GitHub Classroom. refer to the CS15 GitHub Guide for help with GitHub and GitHub Classroom. Once you have the URL of your personal GitHub repository, open the IntelliJ terminal. Move into the **`src/`** folder, then use the command **`git clone <URL>`**.

Once you’ve cloned your personal repository from GitHub, you’ll need to rename the folder from **`lab9-<yourGitHubLogin>`** to just **`lab9`**. To do this, right click on the folder, then go to Refactor, Rename. You will have issues running your code until you make the change.

## The Visualizer
The stencil code contains visualizers (and code related to the visualizers) for the Binary Tree's Sum and Search functionality. Currently, only the **`Sum`** button on the **`Sum`** tab is functional. As you implement the required methods throughout this lab, you will be able to visualize the different traversals and the search method!

## Step 1 : Binary Tree Construction

We are going to learn recursion through a naturally recursive data structure: Binary Trees. Each branch of the tree splits into two smaller branches, and each smaller branch splits into two even smaller branches. The key thing to notice is **every node's *child* node is the *root node* of a *smaller, similar* tree**. This is how we can accomplish the goal recursion sets out to achieve -- solving a problem by breaking that problem into smaller, similar problems.

As referenced in the [slides](https://docs.google.com/presentation/d/1BVieiVG20E25o-IHiL51joDj5weXNIkdtWpOzuLYhHE/edit?usp=sharing), we leverage polymorphism to model our Trees. The **`TreeNode`** and **`EmptyNode`** classes implement the **`ITreeNode`** interface, where a **`TreeNode`** has two **`ITreeNode`** children (a **`left`** and a **`right`** child), and an **`EmptyNode`** represents an empty tree. This allows us to cleanly construct recursive methods on our trees - the base case is handled in the **`EmptyNode`** class, and the recursive step is handled in the **`TreeNode`** class.

In the next section, you will first visualize the recursive method used to sum all values on a Binary Tree. Then, you will practice writing recursive methods yourself to implement Binary Tree traversal and search.

## Step 2 : Binary Tree Summation

Now, in order to get a better understanding of recursion, we are going to trace the summation of a Binary Tree. The first half of this is visualized in the [slides](https://docs.google.com/presentation/d/1BVieiVG20E25o-IHiL51joDj5weXNIkdtWpOzuLYhHE/edit?usp=sharing), but the second half has been left for you to complete on your own.

One of the most difficult recursion concepts to wrap your head around is how the return values operate. Essentially, a line of code cannot be executed until all method calls on that line have been completed.

So in the case of our **`sumTree()`** method, the **`return this.value + this.left.sumTree() + this.right.sumTree()`** line will not be able to fully execute until we have the sum of both the **`this.left`** and **`this.right`** trees. Furthermore, the **`this.right.sumTree()`** will not begin executing until a final value gets returned for **`this.left.sumTree()`** - the code gets executed left to right.

:::info
STOP AND THINK: Would the final return value of **`sumTree`** remain the same if we instead wrote the method body as **`return this.value + this.right.sumTree() + this.left.sumTree()`**?
:::

:::spoiler
Yes, since the sum of the subtrees are independent of one another.
:::

## Step 3 : Binary Tree Traversal

Here is the video for tree traversals for reference: [Video Link](https://drive.google.com/file/d/1c_IJJi0Xcht7_9MEkVRWKpmigq4G7bXf/view?usp=sharing).

### Preorder Traversal

The first traversal of the tree you will implement is the preorder traversal. The base case (which is the same for all of the traversals) is handled in the **`EmptyNode`** class, where we just do nothing as there is nothing to traverse, or look at, on an **`EmptyNode`**. First, you visit the current node. Then, you make the recursive call on the left child, and the recursive call on the right child.

A really good exercise for determining whether you understand recursion is whether you can figure out the order the nodes will be visited. What will they be for preorder?

<img style="display: block; margin: auto; padding-bottom: 30px" src="https://hackmd.io/_uploads/rkzEZmWMyx.png" alt="Step 1" width="300">

:::spoiler
1245367
:::

:::success
**TODO:** Fill in the code for preorder traversal in the **`TreeNode`** class.
:::

### In-Order Traversal

The next traversal of the tree you will implement is the in-order traversal. First, you are going to make a recursive call on the left child of the current node. Then, you visit the current node. Then, you make the recursive call on the right child of the current node.

Once again, try and work out the order of the traversal first. Obviously, we can’t stop you from checking the correct order, but it’s a really good exercise.

:::spoiler
4251637
:::

:::success
TODO: Fill in the code for inorder traversal in the `TreeNode` class.
:::

### Postorder Traversal

Lastly, you are going to round it out with a postorder traversal. First, make recursive call on the left child, then on the right node, then lastly visit the current node.

Once again, try and work out the order of the traversal first. It’s great practice!

:::spoiler
4526731
:::

:::success
TODO: Fill in the code for postorder traversal in the **`TreeNode`** class.
:::

## Step 4 : Binary Search

The last part of this lab will be implementing binary search. We have set up a special type of binary tree called a binary search tree. In a binary search tree, the node values are laid out such that *all of the nodes to the LEFT of a given node have a SMALLER value than that given node.* This means that the root of any binary tree is the median of all the data points in that tree! All of the nodes to the right of a given node have a greater value. Take a look at the tree we have given you and verify that the pattern works!

You will be implementing the binary search tree search algorithm. Because of the special structure of the binary search tree, it is possible to determine if a certain value is within the binary in minimal runtime.

Think about where in your code you should visit the node by calling the visit method in order to display the binary search traversal.

**Note: Only integers can be searched.**

In the **`binarySearch`** method, implement the binary search algorithm. **`target`** is the value we are searching for. The algorithm (in the **`TreeNode`** class) should follow the following pseudocode:

function binarySearch(double target):
    visit the node
    if the value of node equals target:
        return true
    else if target < value of node:
        return recursive call on left child
    else: // reaching else means target > value of node
        return recursive call on right child

Note that the base case is already filled in in the **`EmptyNode`** class, since if we have reached an **`EmptyNode`**, we have not found **`target`** and therefore we return the value **`false`**.

:::success
**TODO:** Fill in the code for **`binarySearch`** in the **`TreeNode`** class.
:::

# Student Opinion Survey
This assignment was updated this year to improve your CS15 learning experience! If you have any feedback for us, please fill out our student opinion form [here](https://forms.gle/YBYFnQjfQ67iRJnW7).