CMU 15-112 Summer 2020: Fundamentals of Programming and Computer Science
Homework 12 (Due Fri 15-Jun, at 5:00pm)

This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.

To start:
1. Create a folder named 'hw12'
2. Download hw12.go
3. Edit hw12.go using VSCode
4. When you are ready, submit hw12.go to Autolab. For this hw, you may submit up to 10 times, but only your last submission counts.
Do not hardcode the test cases in your solutions.
NOTE: For the next few days, assignments in Go will be manually graded.

Background
This assignment uses a recursive data structure called a tree. Each tree has a value and a list of children trees. A visual representation of a tree might look like this:
```
	   0
	 /   \
	1     2
	    / | \
	   3  4  5
```
This is really 6 trees. A tree rooted at 0 with children 1 and 2, a tree rooted at 1 with no children, a tree rooted at 2 with children 3, 4, and 5, etc.
We represent trees with a recursive struct like this:
type Tree struct { Value int Children []Tree }
The struct is recursive since a tree strucct can contain a list of tree structs. The tree above can be represented by the following code:
Tree{0, []Tree { Tree{1, []Tree{}}, Tree{2, []Tree{ Tree{3, []Tree{}}, Tree{4, []Tree{}}, Tree{5, []Tree{}}, }}, }}
In this assignment, we'll be writing recursive functions on trees. Here's an example function that prints out all the values in a tree and its children:
func printValues(T Tree) { fmt.Println(T.Value) for _, subtree := range T.Children { printValues(subtree) } }

treeContains(T Tree, target int) bool [30pts]
Write the function treeContains(T Tree, target int) bool that takes in a tree and a target integer and returns true if the target integer exists anywhere in the tree. For example, if T is the sample tree above, treeContains(T, 0) is true and treeContains(T, 112) is false.

treeValues(T Tree) cs112.IntSet [30pts]
Write the function treeValues(T Tree) cs112.IntSet that takes in a tree and returns a set of all values in that tree. For example, if T is the sample tree above, printing out treeValues(T) gives us {0, 1, 2, 3, 4, 5}.

Study powerset and permutations [10pts]
Take 30 minutes to study powerset, permutations, and mergesort in the notes. Really understand how they work and be able to write them up from scratch. Take out a pencil and paper and practice until you can reproduce them fluently. We won't have a mechanism for veryfing that you complete this section of the homework outside of testing you on the final or future writing sessions. It's up to you to put in the time here!