Lab: 33 - Binary Search Tree and Traversals

Assigned

Wednesday, 15 November 2023

Before you start the lab use the Binary Search Tree interactive visualization written by David Galles at the University of San Francisco to get familiar with BST.

Preparation

As far as I can tell from a quick look at the Java documentation, Java 11 does not have a standard class for a binary search tree; so we will use Weiss’ implementation as a starting point. You will find the classes in the directory /home/jimenezp/csc207/Lab-BinarySearchTree. Copy the files to your computer.

• Create a new Java Project and import the classes into your project.
• Could BinaryNode be implemented as a nested class within BinarySearchTree? What would be the visibility access of the nested BinaryNode class?

Displaying Structure and Contents of a Binary Search Tree

(1/2 point) Neither Weiss’s implementation of BinarySearchTree nor his implementation of BinaryNode overrides the toString method, so that each class simply inherits that method from Object. As a result, their string representations are difficult to decipher. We will make a slightly better set of toString methods that will turn the binary search tree information into a single String for printing.

For example, after creating a binary search tree and inserting the elements 2, 1, and 3, the call to the toString method should return

[[... | 1 | ...] | 2 | [... | 3 | ...]]

• Augment Weiss’s implementation of BinaryNode with a static recursive toString method that returns a string containing a left square bracket, the string representation of the left child node, a vertical bar, the string representation of the element, another vertical bar, the string representation of the right child node, and a right square bracket. When the left or right field of the BinaryNode is null, toString should represent it by the string “null” or “…”. Note that the toString method calls itself as long as there is a left node in a given subtree. After that, it displays the element at the root of the subtree. Then, it calls itself on the right subtree.
• Augment Weiss’s implementation of BinarySearchTree with a toString method that calls the BinaryNode toString method, with the root node as the method argument, and returns the result.

Write out what the string representation of a BinarySearchTree<Integer> containing 42, 39, 61, 58, and 54 should be, and then test your program by building that binary search tree and then invoking toString and printing out the result

[[... | 39 | ...] | 42 | [[[... | 54 | ...] | 58 | ...] | 61 | ...]]

Analyzing Binary Search Trees

In section 19.3 of Weiss’ book, Weiss introduces an important way to measure the “stringiness” or “bushiness” of a non-empty binary search tree: its internal path length, defined as the sum of the depth of its nodes. The depth of a node in a binary tree is defined as 0 if the node is at the root of the tree and otherwise as 1 plus the depth of its parent node.

For example, the internal path length of the bushy tree shown in the following tree is 34

The depth of its root node is 0, and there are two nodes of depth 1, four of depth 2, and eight of depth 3. If the same fifteen nodes were arranged in an unbalanced tree

the tree’s internal path length would be 0 + 1 + 2 + . . . + 14, or 105.

• (1 point) Augment Weiss’s implementation of BinarySearchTree with a public method that computes the tree’s internal path length. Have this public method call a helper recursive method that computes the internal path length. Consider carefully what the parameters of the recursive method should be, i.e., what information it might be useful to pass from one recursive call to another. If you still have difficulties writing the correct code after 10 minutes of working on this problem, read BJP section 17.3 - Common Tree Operations again.

• (1/2 point) Another measure of the stringiness or bushiness of a (non-empty) binary search tree is its height. If the root node of a binary search tree has two non-empty subtrees its height is 1 plus the greater of the heights of those subtrees; if it has one non-empty subtree, its height is 1 plus the height of that subtree; if both of its subtrees are empty, its height is 0. Augment Weiss’s implementation of BinarySearchTree with a method height that computes the tree’s height.

Traversals

Another way to examine the contents of a binary search tree would be to traverse the nodes of the tree, printing each element as it is encountered during the traversal. There are three primary ways of arranging the three fields of a BinaryNode:

• element, left, right (“preorder”)
• left, element, right (“inorder”)
• left, right, element (“postorder”)

Each of these corresponds to a different way of traversing the tree of which the given node is the root. For instance, in a preorder traversal, the element field of the root node would be printed first, and then successive recursive calls to the traversal procedure would be used to print, first, the elements in the left subtree and then the elements in the right subtree.

• (1 point) Implement the postorder traversal as an additional public method postOrder in the BinarySearchTree class. Make this method iterative instead of recursive. Use two stacks to implement the postorder traversal. You will push nodes from the tree onto the first stack onto the second stack. The second stack will be used to print the tree elements in post-order. Think about how the second stack needs to be organized so that it will print the items in the desired order. How to proceed? You could push the tree root into the first stack. At the beginning of each iteration, pop an element at the top of the first stack and push it into the second stack. Then, push the children of a rooted subtree into the first stack in some order. After getting out of the iterations, pop the elements from the second stack. This gives the postorder traversal of a binary search tree.

• How would you update your code if you have to create a inorder or preorder traversal?

Test your postorder traversal by defining a method displayPostOrder that calls postOrder method.

Lab Submission

Submit BinarySearchTree.java, BinaryNode.java and your Tester class along with the output after running your program (1 point).

Remember: Do not use magic numbers, write your code anticipating errors and print user-friendly error messages, all your public methods should be well documented (use Javadoc comments). Please include comments or organize your code and report in a way that will help the grader to find the answer to the exercises or posted questions.

For those with extra time (extra points)

(2 extra points) Now that you have practiced how to create iterative methods to traverse trees. Write a preorder iterator. For this class, we need, a constructor and the methods called hasNext and next (remember, an iterator provides more methods such as remove. The remove method should throw an UnsupportedOperationException).

Write code to test your PreOrderIterator.

Submit the code for your PreOrderIterator class and test code along with the console screenshot after running your program.

Acknowledgements

We are using the BST definitions from the Weiss textbook. Any other code probably comes from Prof. Shervin Hajiamini and John Stone.