CS 112
Spring 2024

Lab 11: Binary trees and search Trees

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:

  1. What is the depth of node E? Of node A?

  2. What is the height of the tree?

  3. If a preorder traversal were used to print the keys, what would the output be?

  4. What would be the output of an inorder traversal?

  5. What would be the output of a postorder traversal?

  6. 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.

  1. Insert the following sequence of keys into an initially empty binary search tree:

    15, 23, 20, 10, 13, 6, 18, 35, 9, 24

  2. What does the tree look like after each of the following deletions, which are carried out in sequence:

    • delete 6
    • delete 15
    • delete 20

    Note: Students in the B1 lecture will cover the deletion algorithm in Friday’s lecture, and they are welcome to wait until after that lecture to try this part of Task 2.

Task 3: Work with the LinkedTree class

Download the following zip file: lab11.zip

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

  1. 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()

    should output:

    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.

  2. 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();

    should output:

    15 
10 23 
6 13 20 35 
9 18 24

    and,

    tree.inorderPrint();

    should output:

    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();

    should output:

    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.

  3. 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?

  4. Implement the method called sumKeysTree() whose header can be found in the LinkedTree class that we’ve given you in the lab11 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() );

    should output:

    24

  5. Now let’s add another method called numEvensAlongPath() that takes a key and uses iteration to compute and return the number of even keys encountered 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 number of even 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 numEvenslongPath() method should work:

    System.out.println( tree.numEvensAlongPath(5) );

    should output:

    2

    because the path from the root node to the 5 node goes from 8 to 4 to 5 and two even keys are encountered along the way.

    We have given you a header for numEvenAlongPath() 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.