Lab 10: Binary trees

Binary Trees
Task 1: Review binary-tree basics
Binary Search Trees
Task 2: Work with binary search trees
Task 3: Work with the LinkedTree class
Balanced Trees
Task 4: 2-3 Trees
Task 5: B Trees
Task 6: Extra questions
Task 7: Submit your work

Binary Trees

Task 1: Review binary-tree basics

Your work for this task should be done on paper. Please show your work to a staff member before you leave the lab.

Consider the following binary tree in which the keys are letters:

What is the depth of node E? Of node A?
What is the height of the tree?
If a preorder traversal were used to print the keys, what would the output be?
What would be the output of an inorder traversal?
What would be the output of a postorder traversal?
What would be the output of a level-order traversal?

Binary Search Trees

Task 2: Work with binary search trees

Your work for this task should also be done on paper.

Insert the following sequence of keys into an initially empty binary search tree:
```
15, 23, 20, 10, 13, 6, 18, 35, 9, 24
```
What does the tree look like after each of the following deletions, which are carried out in sequence:
- delete 6
- delete 15
- delete 20

Task 3: Work with the `LinkedTree` class

Download the following zip file: lab10.zip

Unzip this archive, and you should find a folder named lab10, and within it the files you will need for this lab.

Open LinkedTree.java and compile it.

Write a test program class and add the following (test) statements to a main method:
```
> LinkedTree tree = new LinkedTree();
> tree.insert(30, "this is the root");
> tree.insert(45, "this is one of 30's children");
> tree.insert(15, "this is another of 30's children");
```
Note that each call to insert() specifies two things:
- an integer key
- the value associated with that key (which in all of these cases is a string).
Now try this:
```
> System.out.println( tree.search(45) );
{this is one of 30's children}
```
Note that the call tree.search(45) gives us back the value associated with the key 45 in the tree. More precisely, it gives us back an LLList of values associated with that key (since there could be more than one value), and the toString() method for the LLList is giving us the contents of that list surrounded by curly braces.

Now try this:
```
> tree.levelOrderPrint()
30
15 45
```
Note that the levelOrderPrint() method performs a level-order traversal of the tree and prints the nodes as they are visited; each level of the tree is printed on a separate line. This method doesn’t show you the precise shape of the tree or the edges between nodes, but it gives you some sense of where the nodes are found.
We can use the insertKeys() method to perform a sequence of insertions in which the keys are taken from an array of integers, and the data values are strings that are based on the keys.

For example, to create the initial tree from Task 2, we can do the following:
```
> LinkedTree tree = new LinkedTree();
> int[] keys = {15, 23, 20, 10, 13, 6, 18, 35, 9, 24};
> tree.insertKeys(keys);
> tree.levelOrderPrint();
15 
10 23 
6 13 20 35 
9 18 24
> tree.inorderPrint();
6 9 10 13 15 18 20 23 24 35
```
Note that an inorder traversal visits the keys in order! That happens whenever your tree is a search tree.

We can then check our answers for some of the earlier questions! For example:
```
> tree.delete(6);
> tree.delete(15);
> tree.delete(20);
> tree.levelOrderPrint();
18 
10 23 
9 13 35 
24
```
Note that after these deletions, 18 is the new root node because it replaces the deleted 15. There are also other changes in the bottom two levels of the tree.
Let’s say that we want to compute the sum of all of the keys in a LinkedTree. Should we use recursion or iteration? Why?
Implement the method called sumKeysTree() whose header can be found in the LinkedTree class that we’ve given you in the lab10 folder. Read the comments to see in more detail what this method should do.

To test this method from outside the class, you will actually need to call a separate “wrapper” method called sumKeys() that we have already implemented for you. For example:
```
> LinkedTree tree = new LinkedTree();
> int[] keys = {8, 4, 10, 2};
> tree.insertKeys(keys);
> System.out.println( tree.sumKeys() );
24
```
Now let’s add another method called sumAlongPath() that takes a key and uses iteration to compute and return the sum of the keys along the path from the root to the node containing the specified key. If the key is not in the tree, the method should return the sum of the keys along the path used to determine that the key is missing.

For example, consider this search tree:

We can create this tree as follows:
```
> LinkedTree tree = new LinkedTree();
> int[] keys = {8, 4, 15, 2, 5, 30};
> tree.insertKeys(keys);
```
Given this tree, here’s how your sumAlongPath() method should work:
```
> System.out.println( tree.sumAlongPath(5) );
17
```
Because the path from the root node to the 5 node goes from 8 to 4 to 5, the method returns 8 + 4 + 5 = 17.

Here’s another example:
```
> System.out.println( tree.sumAlongPath(12) );
23
```
In an attempt to find 12, we would follow the path from 8 to 15. If 12 were in the tree, it would be in the left subtree of 15, but 15 doesn’t have a left child. Thus, the method can’t go any further, and it returns 8 + 15 = 23.

We have given you a header for sumAlongPath() in the LinkedTree class. You should now implement this method using a loop. You may find it helpful to consult the loop used by our insert() method as a model for how you can use a loop to traverse a search tree.

Balanced Trees

Recall that a binary tree is balanced if, for each of its nodes, the node’s subtrees have the same height or have heights that differ by 1. This is important because a balanced tree has a height of O(log n). Therefore, for a balanced binary search tree, the worst case for search, insert, and delete is O(h) = O(log n). Giving us the the best worst-case time complexity!

Is the search tree displayed in Task 1 a balanced tree? How about the resulting search tree from Task 2? You should be able to answer why or why not?

Task 4: 2-3 Trees

Create a 2-3 tree from the following sequence
```
45, 1, 25, 12, 26, 44, 4, 50, 43, 21
```
Draw a new tree for each of the following operations
- insert 5
- insert 42
What numbers do I have to visit if I’m searching for
- 44
- 18

Task 5: B Trees

Create a B tree of order 2 from the following sequence
```
27, 55, 51, 68, 2, 16, 7, 35, 22, 30
```
Draw a new tree for each of the following operations
- insert 9
- insert 36
What numbers do I have to visit if I’m searching for
- 16
- 68

Task 6: Extra questions

Is the tree in Task 1 a search tree? Why or why not?
We say that a tree is balanced when, for each node, the node’s subtrees have the same height or have heights that differ by at most one. (An empty subtree can be considered to have a height of -1.)

Is the tree that we gave you in Task 1 balanced?

Is the tree that results from the insertions in Task 2 balanced?
In Task 3.1, we performed the following insertions:
```
> LinkedTree tree = new LinkedTree();
> tree.insert(30, "this is the root");
> tree.insert(45, "this is one of 30's children");
> tree.insert(15, "this is another of 30's children");
```
Does the order of the these insertions matter? Is there another ordering that would produce the same tree? What other trees could we produce if we changed the order of the insertions?

Try to create other trees by varying the order of the insertions. Don’t forget to start by creating a new LinkedTree object before you begin each new sequence of insertions.

Task 7: Submit your work

You should show the paper with your work to the teaching assistant.