# CS1027b Computer Science Fundamentals II

## Lab 11

### General lab instructions to help labs run smoothly

• Read through the lab instructions before coming to the lab.

Upon completion of this lab, you should be able to understand inorder traversals of a Binary Search Tree and observe how Binary Search Trees look when they are built in different ways.

A binary search tree is a binary tree with the following property: For each internal node p the data stored in any node in the left subtree of p is smaller than the data stored in p, and the data stored in any node in the right subtree of p is larger than the data stored in p. See the lecture notes on binary search trees.

### Exercise 1 - Traversing a Binary Search Tree in Descending Order

Recall that an inorder traversal of a Binary Tree does the (recursive) traversal like this: traverse left subtree, visit root, traverse right subtree. For a Binary Search Tree, this results in the tree items being visited in ascending order. To visit the items in descending order, we switch the left and right traversals in the recursive algorithm.

Let us call the method that performs the right, root, left variation of inorder traversal iteratorInOrderDescending. You need to create class IterableBinarySearchTreeList, where you will implement the following two methods:

• public Iterator iteratorInOrderDescending(), which returns an iterator that iterates over all elements in the tree in descending order. Hint: see the iteratorInOrder method in LinkedBinaryTree. You can copy its code to this method, and change it to use your inorderDescending method.
• private inorderDescending(BinaryTreeNode node, ArrayUnorderedList tempList), which performs a recursive inorder traversal in descending order. Hint: this is nearly identical to the inorder method in LinkedBinaryTree. Here, instead of going left to right, we want to go right to left.

### Exercise 2 - Creating a Balanced Binary Search Tree List

Download the files BuildBSTList.java and iteratorLevelOrder.txt and put the code of the iteratorLevelOrder method into your LinkedBinaryTree.java from Lab 10 (this is the only method you did not complete in Lab 10). Note that it requires several classes to compile; we provide most of them here.

BuildBSTList.java is an (incomplete) program that creates an ArrayOrderedList storing the integers from 1 to 10, and then builds a BinarySearchTreeList by just taking the items from the ordered list (in increasing order) and adding them one by one to the binary search tree. What do you expect that the binary search tree will look like? This will be confirmed when you complete the program and run it; it will print the content of the nodes of the tree in level-order. You should look at the output produced by the program and draw on a piece of paper the corresponding tree.

The program then builds another BinarySearchTreeList by calling method buildBalanced that tries to build a tree where either both subtrees of an internal node have the same height or they differ in height by at most 1. (This tree is called a balanced tree.) The heart of this method is method buildBalancedRec that you need to write. This is a recursive algorithm that receives 4 parameters: an array tempArr of integers, two integer values start and end, and a BinarySearchTreeList object bstList. The algorithm works as follows:
• The base case is when start > end. The algorithm does not need to do anything in this case.
• The reursive case happens when start <= end. In this situation the values in tempArr[start],..,tmpArr[end] need to be stored in bstList. To do this, fist comput the postion of the middle element in the subarray tempArr[start],..,tempArr[end] (middle = (start+end)/2). Add tempArr[mid] to bstList and then make two recursive calls: One to store the elements tempArr[start],..,tempArr[mid-1] into bstList and the other to store the elements tempArr[mid+1],..,tempArr[end] into bstList.

Run your completed program and note the difference in the level-order representation of the first tree created (by just adding the items in order) and the second tree created (by adding the items so that the tree is as balanced as possible). Draw a picture of the two trees from the level-order representation, and show it to the TA.

The program will finally call your method iteratorInOrderDescending on the second tree. Verify that the values stored in the tree are printed in decreasing order of value.