Data Structures and Algorithms
COMP 2140
Department of Computer Science
University of Manitoba
Assignment 4: Trees due Wednesday November 19 by 12:00 pm (noon)
Objective
This assignment deals with binary trees. An instance of the class BinaryTree is a binary
tree composed of nodes that are instances of the class BinTreeNode.
Deliverables and Hand-In Instructions
Log in to Desire2Learn and select COMP2140 > Assessments > Dropbox > Assignment 4.
Your solution must be submitted electronically using Desire2Learn. Solutions submitted by
email will not be accepted. Submit one le named A4<your last name><your student
number>.zip that contains the le BinaryTree.java with your code inserted and your
written answers to Questions 3, 5, and 7 in the comments preceding the methods graphAux,
methodA, and methodB, respectively. Please do NOT include anything else in the .zip le.
Marks may be deducted or a grade of zero given if these instructions are not followed.
In addition to the le BinaryTree.java, you will require the les Stack.java, Queue.java,
DNode.java, and EmptyStackQueueException.java. An additional class Example.java is
provided. You will modify and submit BinaryTree.java. You can also modify the le
Example.java to test your code, but you should not need to modify any of the other les.
These les are available on Desire2Learn in a .zip le. Students can choose whether or not
to use generic types in this assignment. Two versions of the les are provided, with and
without generic types, in A4generics.zip and A4noGenerics.zip, respectively; use only
one of the two. No additional marks will be awarded for using generic types.
Programming Standards
When writing code for this course, follow the programming standards available on this
course's website on Desire2Learn. Failure to do so will result in the loss of marks.
Honesty Declaration
Your assignment (and any other work in this course) will not be graded unless you have
submitted a blanket honesty declaration. You can verify whether you have submitted an
honesty declaration under \grades" on Desire2Learn.
Assignment
1. Add code to implement the method isBST in the class BinaryTree such that it returns
true if and only if the keys in the tree are in binary search tree ordering.
Fall 2014, Assignment 4 page 1Data Structures and Algorithms
COMP 2140
Department of Computer Science
University of Manitoba
Hint: Write a recursive helper method that performs an in-order traversal and, upon
visiting each node, inserts that node's key into a queue. After completing the traversal,
verify the order of keys in the queue.
Generic types: If you are using generic types in your code (using generic types is
optional) you will need to use the compareTo method to compare keys. For example,
if a and b are instances of BinTreeNode, and each tree node's generic type <E> is an
Integer (as <E> is used in the class Example), then
a.getElem().compareTo(b.getElem()) == 0 when a's key is equal to b's key
a.getElem().compareTo(b.getElem()) < 0 when a's key is less than to b's key
a.getElem().compareTo(b.getElem()) > 0 when a's key is greater than to b's key
This requires that the generic type E implement the interface Comparable (as does the
class Integer).
2. Add code to implement the method isLeaf in the class BinTreeNode such that it
returns true if and only if the node is a leaf of the tree.
3. Identify the type of tree traversal implemented by the method graphAux called by the
method graph. Add your written answer to the comments before the body of method
methodA in the le binaryTree.java.
4. Add code to the method methodA in the class BinaryTree that does the following:
(a) Declare and instantiate a new (empty) stack whose elements will be instances of
the class BinTreeNode.
(b) Push the root of the binary tree onto the stack.
(c) Write a while loop that terminates once the stack is empty.
(d) Each iteration of the loop should do the following:
Pop the stack.
If the popped item is not null, then print the element, push its left child, and
push its right child onto the stack.
This method should be an accessor method. That is, none of the instance variables
should be modi ed.
5. Describe the outcome of a call to methodA on a binary tree. Add your written answer
to the comments before the body of method methodA in the le binaryTree.java.
6. Add code to the method methodB in the class BinaryTree that does the following:
(a) Declare and instantiate a new (empty) queue whose elements will be instances of
the class BinTreeNode.
(b) Enqueue the root of the binary tree to the queue.
(c) Write a while loop that terminates once the queue is empty.
Fall 2014, Assignment 4 page 2Data Structures and Algorithms
COMP 2140
Department of Computer Science
University of Manitoba
(d) Each iteration of the loop should do the following:
Dequeue an item from the queue.
If the dequeued item is not null, then print the element, enqueue its left child,
and enqueue its right child to the queue.
This method should be an accessor method. That is, none of the instance variables
should be modi ed.
7. Describe the outcome of a call to methodB on a binary tree. Add your written answer
to the comments before the body of method methodA in the le binaryTree.java.
8. Augment the class BinaryTree with an additional private data member int size that
maintains the number of nodes in the tree. This will require changes to the constructors
as well as to the method insert. Add a public accessor method getSize to return
the value of size.
9. Implement the body of method numLeaves such that it returns the number of leaves
in the tree. If the tree is empty, then numLeaves should return 0. If the tree contains
a single node, then numLeaves should return 1. You may use a helper method.
10. Implement the body of method numInternal such that it returns the number of in-
ternal nodes in the tree. If the tree is empty or the tree contains a single node, then
numInternal should return 0. Hint: You can minimize the amount of new code re-
quired by using your solutions to Questions 8 and 9.
11. Augment the class BinTreeNode with an additional private data member int subtreeSize
that maintains the number of nodes in the subtree rooted at that node (including it-
self). Thus, a leaf node should store the value 1. Modify the accessor and modi er
methods getSubtreeSize and setSubtreeSize in the class BinTreeNode to get and
set the value of subtreeSize. The method getSubtreeSize should simply return the
value of subtreeSize (i.e., you can remove the code that is currently in that method).
The method setSubtreeSize should take a single integer parameter to which the new
value is set.
12. Write the body of method computeSubtreeSize in the class BinaryTree that re-
cursively counts the number of nodes in the subtree rooted at node and updates the
corresponding instance variable subtreeSize described in Question 11. The computed
value should be returned.
13. Write the body of method isBalanced in the class BinaryTree such that it returns
true if the sizes of the left and right subtrees of every node di er at most by a factor
of two. That is, if the subtrees of node have respective sizes a and b (measured by the
number of nodes in each subtree), then b=2 a 2b and, equivalently, a=2 b 2a.
This may require using a helper method. Your method can assume that the values
returned by method getSubtreeSize are correct.
Fall 2014, Assignment 4 page 3