Introduction
Requirement
Lab 4 November 15–17
Each student is to attend the lab section in which he/she is registered. It is recommended that students
read the lab assignment beforehand to familiarize themselves with the material. Students should have ample
time to complete the lab assignment during the lab time. Completed lab assignments will be graded by the
teaching assistant during the lab. Labs cannot be submitted after the completion of the lab nor during a
lab session other than the one in which the student is registered.
Lab Assignment
The questions below require you to edit the files BST.java and TreeNode.java. The additional file DictionaryADT.java
declares the Dictionary abstract data type interface; this file should not be modified. The file BSTTest.java
is provided to test your code.
1. Complete the body of the method isLeaf in the class TreeNode such that it returns true if the node
is a leaf.
2. The method numLeaves in the class BST is intended to return the number of leaves in the tree or 0 if the
tree is empty. Note that a tree containing a single node has one leaf (which is also its root). Complete
the body of the helper method numLeavesAux in the class BST such that it returns the number of leaves
in the subtree rooted at node. Your code should be recursive.
3. The helper method heightSubtree in the class BST is intended to return the height of the subtree
rooted at node. The existing code correctly computes the recursive height for non-empty subtree. You
are to edit the code such that the base case (i.e., when the subtree is empty) returns the correct height.
4. The method isHeightBalanced in the class BST is intended to return true if the tree is height balanced.
Complete the body of the helper method isHeightBalancedAux in the class BST such that it returns
true if the subtree rooted at node is height balanced. That is, the subtree is height balanced if for each
node a in the subtree rooted at node (including the case a = node),
|height(a.left) − height(a.right)| ≤ 1.
Your code should be recursive. Your method should return true if the tree is empty.