CS1027b Computer Science Fundamentals II

Lab 11

General lab instructions to help labs run smoothly

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:

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:

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.