Using Trees

Introduction

This lab will familiarize you with the Tree ADT.  You'll be tasked with implementing some basic tree functionality that will solidify your understanding of how trees work by building a binary tree and supporting functions.  Also note that you'll need to use recursion to accomplish some parts in the most efficient manner.  

Be sure to read and follow the instructions carefully to ensure the highest possible grade!

Setup

For this lab, you'll need these files: lab10_files.

Once you've downloaded and unzipped the archive, you should have several files ready to go.  In their current state, the program will compile and run without error!  Don't worry...I've left plenty of work for you.  But before you start hacking away at your keyboard, compile the program to reassure yourself that there are no problems with the code I've provided.  Here's the command to compile the code.  This will not change throughout the lab, and is what I will use when testing your submission:

g++ -o temp treelab.cpp

Once you've compiled the program, run it by passing input1.txt into stdin. You should see this:

Notice that the Max Value, Min Value and Max Depth are -1.  You'll fix that shortly.  Now that you've confirmed the program works, you can be assured that any errors (e.g. segmentation faults) from this point forward are the result of something you've added.

Part 1 (60 points)

The way the main function is written, the first integer value is used to create the root Node (see TreeNode.h).  After that, each integer is inserted into the Tree using the insertInt() function found at the top of the treelab.cpp file.  Your task is to complete the insertInt function by implementing the insert functionality needed to create a binary tree using the methods provided to you by the Tree class (defined in Tree.h), and following these guidelines:

• Starting at the root Node, determine if the value of the integer to be inserted is less than or greater than the root value.  If it's less, it is inserted to the left of root.  If it's greater, it's inserted to the right.
• If inserting to the left or right and a child node already exists in that position, insert to the left or right of that node based on whether the value is greater or less than the child node.  Continue in this fashion until the value can be inserted into the Tree.  
• No Node can have more that two children.
• No duplicate values should be placed in the Tree.

For example, given the values (in this order) [50, 25, 75, 15, 20], the Tree would be represented like this:

However, changing the order of the values to [50, 15, 25, 75, 20] would result in the following Tree structure:

Notice how the values in the left subtree have changed based on the order elements were inserted into the Tree.  The prettyPrint function (provided as part of TreeNode.h) can be used to verify proper tree placement when testing your solution.  See the sample output below for what the Tree structure should look like when using the provided file input1.txt.

Part 2 (15 points)

Your next task is to implement the getMax() and getMin() functions at the top of treelab.cpp following the below specifications:  

• Both should return an integer value representing the maximum or minimum integer value currently stored in the Tree.
• Both functions should return 0 when called on an empty Tree.

For example, both samples shown in Part 1 would have a Max value of 75, and a Min value of 15.

Part 3 (25 points)

Your final task is to implement the maxDepth() function found at the bottom of Tree.h.  This function should determine the maximum depth of the Tree from a given node.  Remember from lecture that we start counting depth from 0, so if maxDepth is called from the Tree's root node, and the Tree has no other nodes, it should return 0.  

For example, both Trees shown in Part 1 have a maximum depth of 3.

Sample Output

If you've implemented all three parts correctly, your final output using input1.txt should look like this:

Your output using input2.txt should look like this:

Hints

• When implementing insertInt, getMax and getMin, be sure to keep track of where the "current" pointer is pointing.
• Don't touch any other files, or any part of code that isn't marked appropriately (including the main function).  
• Don't forget to test your solution using all edge cases.  For example:
  • An empty tree
  • A tree with only one Node

Deliverables

Due: 2359, Monday 19 Nov 2018

Submit your modified source code via the the submisison website: submit.cs.usna.edu.

Specifically:

• treelab.cpp
• Tree.h

~/bin/submit -c=SI221 -p=Lab10 treelab.cpp Tree.h