CS 112
Spring 2026
  • Home
  • Syllabus
  • Labs
  • Problem Sets
  • Staff
  • Office Hours
  • Resources
  • Collaboration
  • Policies
  • Lectures
  • Piazza
  • Gradescope

Lab 12: Binary trees and search 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: Extra questions

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: lab12.zip

Unzip this archive, and you should find a folder named lab12, 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 lab12 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

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

  1. Create a 2-3 tree from the following sequence

    45, 1, 25, 12, 26, 44, 4, 50, 43, 21

  2. Draw a new tree for each of the following operations

    • insert 5
    • insert 42

  3. What numbers do I have to visit if I’m searching for

    • 44
    • 18

Task 5: Extra questions

  1. Is the tree in Task 1 a search tree? Why or why not?

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

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

Last updated on April 15, 2026.