lab_trees

Assignment Description

In this lab we’ll explore some cool helper functions for binary trees, learn about creating helper functions and thinking both iteratively and recursively, and hopefully see some fancy ascii trees on the terminal!

Lab Insight

Trees are a very powerful structure for lookups and finding data quickly. Examples of use cases for this data structure includes search engine optimization and fast sorted data retrieval. CS 410, Text Information Systems, is a course that delves into topics involving text manipulation such as test search lookups. Trees can even be used for syntax and language grammar analysis which relates a lot with CS 421, Programming Languages and Compilers.

Checking Out the Code

All assignments will be distributed via our release repo on github this semester. You will need to have set up your git directory to have our release as a remote repo as described in our git set up

You can merge the assignments as they are released into your personal repo with

git pull --no-edit --no-rebase release main
git push

if you are using multiple machines you may need to use the following to allow them to work correcly.

git pull --no-edit --no-rebase release main --allow-unrelated-histories
git push

The first git command will fetch and merge changes from the main branch on your remote repository named release into your personal. The --no-edit flag automatically generates a commit message for you, and the--no-rebase flag will merge the upstream branch into the current branch. Generally, these two flags shouldn’t be used, but are included for ease of merging assignments into your repo.

The second command will push to origin (your personal), which will allow it to track the new changes from release.

You will need to run these commands for every assignment that is released.

All the files for this lab are in the lab_trees directory.

Preparing Your Code

This semester for MPs we are using CMake rather than just make. This allows for us to use libraries such as Catch2 that can be installed in your system rather than providing them with each assignment. This change does mean that for each assignment you need to use CMake to build your own custom makefiles. To do this you need to run the following in the base directory of the assignment. Which in this assignment is the lab_trees directory.

mkdir build
cd build

This first makes a new directory in your assignment directory called build. This is where you will actually build the assignment and then moves to that directory. This is not included in the provided code since we are following industry standard practices and you would normally exclude the build directory from any source control system.

Now you need to actually run CMake as follows.

cmake ..

This runs CMake to initialize the current directory which is the build directory you just made as the location to build the assignment. The one argument to CMake here is .. which referes to the parent of the current directory which in this case is top of the assignment. This directory has the files CMake needs to setup your assignment to be build.

At this point you can in the build directory run make as described to build the various programs for the MP.

Testing Your Code

To test your code, compile using make:

make

Then run it with:

./tree color

You will see that the output is colored — green means correct output, red means incorrect output, and underlined red means expected output that was not present. This mode is a bit experimental, and it might cause problems with your own debugging output (or other problems in general). To turn it off, simply leave off the “color” argument:

./tree

Helper Functions and Recursion

You’ll want to be thinking about the following problems recursively. To do this, though, you’ll have to make your own helper functions to help implement the functions, so that you can recursively act differently on different nodes. There is room in the .h file for you to declare these extra functions. A helper function stub for height() has been provided for you.

The height() Function

There is a function called height() that returns the height of the binary tree. Recall that the height of a binary tree is just the length of the longest path from the root to a leaf, and that the height of an empty tree is -1.

We have implemented height() for you (see binarytree.cpp) to help you get a sense of recursive functions. Please read through the code, and ask questions if you are unsure of how it finds the height of a tree.

The printLeftToRight() Function

There is a function called printLeftToRight() that prints out the values of the nodes of a binary tree in order. That is, everything to the left of a node will be printed out before that node itself, and everything to the right of a node will be printed out after that node.

We have implemented printLeftToRight() for you (see binarytree.cpp). Please read through the code, and ask questions if you are unsure of how it works. Note that printLeftToRight() uses an in-order-traversal to print out the nodes of a tree. You will need to use one of the three traversals covered in lecture for some of the following functions.

The mirror() Function

The mirror() function should flip our tree over a vertical axis, modifying the tree itself (not creating a flipped copy).

For example, if our original tree was

                        ______ 8 ______
                 ______/               \______
            __ 5 __                            9 __
         __/       \__                             \__
       2               7                               10
     /   \           /
   1       4       6
          /
         3

Our mirrored tree would be

                        ______ 8 ______
                 ______/               \______
            __ 9                            __ 5 __
         __/                             __/       \__
       10                              7               2
                                         \           /   \
                                           6       4       1
                                                    \
                                                     3

The TreeTraversals Family

Class Hierarchy for TreeTraversals family:

We’ve already implemented PreorderTraversal class for you (see TreeTraversals/PreorderTraversal.h). Read the constructor and operator++ of TreeTraversal::Iterator to understand how they interact with TreeTraversals. Notice that TreeTraversal and TreeTraversal::Iterator are two separate classes. You can read more about iterators here. Your task is to implement the the following constructors and functions for InorderTraversal class:

• InorderTraversal(typename BinaryTree<T>::Node* root)
• void add(typename BinaryTree<T>::Node *& treeNode)

Test your InorderTraversal class:

./traversal

The isOrdered() Family

The isOrdered() family includes two functions, one should be implemented iteratively, the other should be implemented recursively. Both functions return true if an in-order traversal of the tree would produce a nondecreasing list output values, and false otherwise. (This is also the criterion for a binary tree to be a binary search tree.)

For example, isOrdered() should return true on the following tree:

           __ 5 __
        __/       \__
      1               8
        \
          2
           \
            4

but false for

           __ 5 __
        __/       \__
      1               8
        \
          2
           \
            11

You’ll need to implement the following functions:

• bool isOrderedIterative() const
• bool isOrderedRecursive() const

Hint: What conditions need to be true for a tree to be in order (as defined above)? How can we check this iteratively? (Your Iterator class might help) How can we check this recursively? You might want to write your own helper functions for this exercise.

Testing Your Code with Catch

Run the Catch tests as follows (this requires your code to compile when run simply as make):

make test
./test

Submitting Your Work

The following files are used in grading:

• binarytree.h
• binarytree.hpp
• InorderTraversal.h

All other files including any testing files you have added will not be used for grading.

Good luck!

Thanks to Nick Parlante/Stanford, Princeton’s CS 126, and CS 473 Spring 2011 for the exercises and inspiration.