COMP 1006 Winter 2020 Assignment 03
Mutable Object Structures: Trees
Due Thu. March 12 Tue Mar 17 by 10:00pm in culearn
Assignment Revisions and Corrections will be noted here.
Rev 1: I’ve added a clarification to indicate that your solutions are intended to use recursion as you were expected to do in tutorials 06 and 07. That is, we will not accept solutions that just solve the problems by iterating over an Arraylist of all the nodes. You ARE expected to traverse the tree and make use of recursion -otherwise it defeats the purpose of having a tree in the first place. Note the assignment is being extended a few days but the due date of the next assignment 4 will remain the same. Not recursing the tree will be considered a violation of R0.3
Mutable Object Structures: Trees
In this assignment you will work with, and modify, object structures that grow and shrink over the course of their use. We will use the “offspring” tree presented in Tutorial 06 as our mutable type. It is represented by a single class: TreeNode. You will also get more practice doing recursion and basic string processing in Java.
IMPORTANT: To do this tutorial you must first have set up your machine by installing java JDK 12.x.x, IntelliJ IDE and run through the “Setting Up Intelij for JavaFX” in the 00 Hello World section of the course notes as was done for tutorial 03. These notes explain how to obtain and install the JavaFX components you will need to compile the demo code.
Marking: This assignment is based on 15 design requirements numbered R1.1…R4.3 for a total of 30 marks.
Marks are awarded, or deducted, based on requirements as follows:
Req Type
Assignment Grading
R0.x
Critical Submission and Intent Requirements. Assignment gets 0 if any critical submission
requirement (shown in red) is not met.
R0.x
Good Practice Requirements. You lose 2 marks for each good practice
requirement (shown in amber) not met.
Rx.x
Design Requirements. You earn 2 marks for each design requirement (green) satisfied and well implemented; 1 mark if it’s partly met or met but not well implemented; and 0 if it’s not met or attempted.
Submission and Good Programming Practice Requirements
The following requirements pertain to all your assignments regardless of what your application is supposed to do (i.e. regardless of the design requirements). These requirements are to ensure that your code is usable, readable, and maintainable.
R0.0 UNIQUENESS REQUIREMENT. The solution and code you submit MUST be unique. That is, it cannot be a copy of, or be too similar to, someone else’s code, or other code found elsewhere. You are, however, free to use any code posted on our course website as part of our assignment solution. [Assignment mark =0 if this requirement is not met.]
R0.1 CODE SUBMISSION ORGANIZATION AND COMPILATION: You should submit all the code files and data files that make up your Intelij java project. The TA’s will open your project with Intelij, build the project and then run the application from your class whose name contains the substring “Main”.
IMPORTANT: The assignment mark is 0 if your code does not compile and launch.
[Assignment mark =0 if this requirement is not met.]
R0.2 README FILE: Your submission MUST include a README.txt file telling the TA how to launch and run your app. The TA should not have to look into your code to figure out how to start up your app. Your README.txt MUST contain the following:
• Your name, student number and email address and if you are working with a partner then their name, student number and email address as well.
• Version: The java JDK version you were compiling your code with.
• Setup Instructions: Are there any setup instructions like making sure a data file is located in a special place. Typically this section might just say “None”.
• Launch and Testing: Tell us which class in your app has your main() function in it. You should only have one main() function in your application. If there are specific tests you want the TA to perform tell us what the steps are you want them to perform.
• Issues: List any issues that you want the marker to be aware of. In particular, tell us what requirements you did not implement or that you know are not working correctly in the submitted code. Here you are giving us your own assessment of your app.
•
R0.3 INTENT REQUIREMENT. Your solution must be in the spirit of the intent of the assignment. For example, if you hard-code answers rather than writing code that solves the intended problems you would be violating the assignment intent.
R0.4 VARIABLE AND FUNCTION NAMES: All of your variables, classes and methods should have meaningful names that reflect their purpose. Don’t follow the convention common in math courses where they say things like: “let x be the number of customers and let y be the number of products…”. Instead call your variables numberOfCustomers or numberOfProducts. Your program should not have any variables called “x” unless there is a good reason for them to be called “x”. (One exception: It’s OK to call simple for-loop counters i,j and k etc. when the context is clear and VERY localized.)
Remember: any fool can write code that a computer will understand; the goal is to write code that we can understand. [Minus 2 marks from assignment if this requirement is not met.]
R0.5 COMMENTS: Comments in your code must coincide with what the code actually does. It is a common bug to modify, or cut-and-paste code, and forget to modify the comments and so you end up with comments that say one thing and code that actually does another. Don’t over-comment your code – instead choose good variable names and function names that make the code “self commenting”. Don’t be reluctant to create local variables so that the variable name provides more clarity -there is no prize for having the fewest lines of code. [Minus 2 marks from assignment if this requirement is not met.]
R0.6 CITATION REQUIREMENT: If you use code from other sources you should cite the source in comments that appear with the code. If the source is an internet website then put the URL in the comments. You may use bits of code from outside sources but this may not form the complete solution you are handing in.You DON’T have to cite demo code we provide on the course web site or with tutorials and assignments, however that code should not be used for things you post publicly (like on GitHub). [Minus 2 marks from assignment if this requirement is not met.]
VERY IMPORTANT: Any sample code fragments provided may have bugs (although none are put there intentionally). You must be prepared to find errors in the requirements and sample code. Please report errors so they can be fixed and an assignment revision posted.
Design Requirements

The assignment demo code provides a starting point for an app that allows you to create an “offspring” tree. It implements the tree using only a TreeNode class. The main application class hard-codes an example tree in the start() method used to initialize the app. You will, however, remove this hard-code and instead allow the user to build a tree using the textfield and “Insert” button as described in the requirements below. The user will also be able to remove nodes with the “Remove” button and locate and highlight nodes with the “Find” button. Finally we want you to add animation so that changes to the tree are easier to follow. This assignment is based on the code presented in Tutorial 06.
Feel free to change the node shapes, colors, labels etc. to make it look the way you like.
Note: see screen capture video below which illustrates a possible solution.
Rev 1: I’ve added a clarification to indicate that your solutions are intended to use recursion as you were expected to do in tutorials 06 and 07. That is, we will not accept solutions that just solve the problems by iterating over an Arraylist of all the nodes. You ARE expected to traverse the tree and make use of recursion -otherwise it defeats the purpose of having a tree in the first place. Note the assignment is being extended a few days but the due date of the next assignment 4 will remain the same. Not recursing the tree will be considered a violation of R0.3
Node Creation Requirements
R1.1 You should be able to add nodes to the tree by typing the node information in the application text field and pressing the “Insert” button subject to the following requirements.
R1.2 If the application is blank (has no tree) you would be able to type “Louis male” in the text field, click the “Insert” button (or just hit the Enter key) and it should create a new tree rooted at a male-gender node with label “Louis”. Similarly if the user typed “Louise female” a female node should be created.
R1.3 If you type “Sam son of Louis” in the text field and hit “Insert” a new node labelled “Sam” should be created that is a male child of a node “Louis” that already exists in the tree. If no “Louis” node currently exists the request can be ignored. If more than one “Louis” node exists then you can choose whatever one you want.
R1.4 If you type “Sue daughter of Louis” in the text field and hit “Insert” a new node labelled “Sue” should be created that is a female child of a node “Louis” that already exists in the tree. If no “Louis” node currently exists the request can be ignored. If more than one “Louis” node exists then you can choose whatever one you want.
Node Removal Requirements
R2.1 You should be able to remove nodes from the tree by typing the node information in the application text field and pressing the “Remove” button subject to the following requirements. Note you can only remove leaf nodes (nodes that have no children).
R2.2 If you type “Sam” in the text field and then hit the “Remove” button a node whose label is “Sam” and which is a leaf node (has no children) should be removed. If there is no leaf node labeled “Sam” the request can be ignored.
R2.3 If you type “Sam son of Louis” in the text field and then hit the “Remove” button a node whose label is “Sam” and who is both a leaf node and the male child of a node labeled “Louis” should be removed. If there is no such node the request should be ignored.
R2.4 If you type “Sue daughter of Louis” in the text field and then hit the “Remove” button a node whose label is “Sue” and who is both a leaf node and the female child of a node labeled “Louis” should be removed. If there is no such node the request should be ignored.
Node Search Requirements
R3.1 You should be able to find and highlight nodes in the tree by typing the node information in the application text field and pressing the “Find” button subject to the following requirements.
R3.2 If you type “Sam” in the text field and then click the “Find” button any single node whose label is “Sam” should be highlighted. (Drawn in the Drawable interface’s highlight colour).
R3.3 If you type “Sam son of Louis” in the text field and then click the “Find” button a single node whose label is “Sam” and who is the male child of a node labeled “Louis” should be highlighted. If there is no such node the request should be ingnored.
R3.4 If you type “Sue daughter of Louis” in the text field and then click the “Find” button a single node whose label is “Sue” and who is the female child of a node labeled “Louis” should be highlighted. If there is no such node the request should be ingnored.
Animation Requirements
If a mutable structure changes suddenly it can be hard to follow what the changes were. But if the structure “slides” or “morphs” into its new configuration then the changes are easy to follow and believable. We want you to implement this. The easiest way is probably to have two locations associated with each node: a target location and a current location and with each timer event the node could be moved, or drawn, closer towards its target location. But there is no intended right way to do this -here is where you can be creative.
R4.1 When the animation timer is running (controlled by the provided menu items) insertion and removal of nodes should cause the restructuring of the tree to be animated over time (see the screen capture video below). When the animation timer is not running the changes can be abrupt.
R4.2 When animation is running and a new child node is inserted, the child node should start at its parent’s location and “slide” to its proper location over the course of time (a few seconds). Other nodes should also slide to their new intended locations.
R4.3 When a node is removed, the node can just disappear but any repositioning of the remaining nodes should happen over time with them sliding into their new positions.
Here is a screen capture video showing how your code might behave once you have finished the assignment.
Your browser does not support the video tag.